理论上4种颜色就够了.地图的四色问题嘛!
可能会有多组解。用递归（dfs)就可以输出所有解了。
地图着色算法C语言源代码
前面我写了一个地图着色（即四色原理）的C源代码。
写完以后想了一下，感觉还不完善，因为从实际操作的角度来考虑，四种可用的颜色放在旁边，不同的人可能会有不同的选择顺序，另外，不同的人可能会选择不同的城市作为着色的起点，而当时的程序没有考虑这个问题。于是，把程序修改为下面的样子，还请同行分析并指出代码中的不足之处：
＃i nclude <stdio.h>
#define N 21
int allcolor[4]/*可用的颜色*/
int ok(int metro[N][N],int r_color[N],int current)
{/*ok函数和下面的go函数和原来的一样,保留用来比较两种算法*/
int j
for(j=1j<currentj++)
if(metro[current][j]==1&&r_color[j]==r_color[current])
return 0
return 1
}
void go(int metro[N][N],int r_color[N],int sum,int current)
{
int i
if(current<=sum)
for(i=1i<=4i++)
{
r_color[current]=i
if(ok(metro,r_color,current))
{
go(metro,r_color,sum,current+1)
return
}
}
}
void color(int metro[N][N],int r_color[N],int sum,int start)
{
int i,j,k
r_color[start]=allcolor[0]
for(i=start+1i!=starti=(i+1)%(sum+1))/*把所有编号看作一个环*/
if(i==0)/*城市号从1开始编号,故跳过0编号*/
continue
else
for(j=0j<4j++)
{
r_color[i]=allcolor[j]/*选取下一种颜色,根据allcolor中颜色顺序不同，结果不同*/
for(k=1k<ik++)/*检查是否有冲突，感觉还可以改进，如使用禁忌搜索法*/
if(metro[i][k]==1&&r_color[k]==r_color[i])
break
if(k>=i)
break
}
}
void main()
{
int r_color[N]={0}
int t_color[N]={0}
int i
int start/*着色的起点*/
int metro[N][N]={{0},
{0,1,1,1,1,1,1},
{0,1,1,1,1},
{0,1,1,1,0,0,1},
{0,1,1,0,1,1},
{0,1,0,0,1,1,1,0,0,1,0,0,0,0,0,0,1},
{0,1,0,1,0,1,1,1,1,1},
{0,0,0,0,0,0,1,1,1},
{0,0,0,0,0,0,1,1,1,1,0,0,1},
{0,0,0,0,0,1,1,0,1,1,0,0,1,1,1,0,1},
{0,0,0,0,0,0,0,0,0,0,1,1,0,1,0,1,0,0,0,1},
{0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1},
{0,0,0,0,0,0,0,0,1,1,0,1,1,1,0,0,0,0,0,1,1},
{0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,1,0,0,0,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,1,1,1,0,1},
{0,0,0,0,1,0,0,0,1,0,0,0,0,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1},
{0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,1,0,0,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1}}
allcolor[0]=1allcolor[1]=2allcolor[2]=3allcolor[3]=4/*选色顺序，顺序不同，结果不同*/
start=1
/* clrscr()*/
printf("\nAll color is:\n")
for(i=0i<4i++)/*当前选色顺序*/
printf("%d",allcolor[i])
go(metro,r_color,20,1)
printf("\nFirst method:\n")
for(i=1i<=20i++)
printf("%3d",r_color[i])
color(metro,t_color,20,start)
printf("\nSecond method:\n")
printf("\nAnd the start metro is:%d\n",start)
for(i=1i<=20i++)
printf("%3d",t_color[i])
}
说是人性化着色，其实还有一个问题没有考虑，那就是操作员跳跃式着色，就像大家玩“扫雷”游戏一样。其实也容易实现，可以像定义选色顺序一样定义着色顺序。
1、描述一下具体输入，比如上图一，长这样？？还是邻接矩阵？还是直接一堆边？
54 2
1 5
5
1 5
2 3 4
2、你这个问题本质上属于二分图染色。。你可以百度找一下资料
我写过二分图匹配的题可以参考，，，。提交：
代码网页链接
//二分图最大匹配 O(V*E) Test#include<iostream>#include<vector>#include<cstring>using namespace stdconst int N = 3e6vector<int>G[N]int po[N], book[N], ansint find(int u){for(int i = 0 i < G[u].size() i++){
int v = G[u][i]
if(!book[v]){
book[v] = 1
if(po[v]==0||find(po[v])){
po[v] = u
return true
}
}
}
return false}int main(){
int nl, nr, m
cin>>nl>>nr>>m
for(int i = 1 i <= m i++){
int x, y cin>>x>>y
G[y].push_back(x)
}
for(int i = 1 i <= nr i++){
memset(book,0,sizeof(book))
if(find(i)){
ans++
}
}
cout<<ans<<"\n"
for(int i = 1 i <= nl i++)cout<<po[i]<<" "
return 0}
从一个省开始，给它涂上任意一种颜色1，遍历它旁边的省份，涂上与已经涂色并于他相邻的省份不同的颜色就行了。理论上4种颜色就够了.地图的四色问题嘛!
可能会有多组解。用递归（dfs)就可以输出所有解了。
地图着色算法C语言源代码
前面我写了一个地图着色（即四色原理）的C源代码。
写完以后想了一下，感觉还不完善，因为从实际操作的角度来考虑，四种可用的颜色放在旁边，不同的人可能会有不同的选择顺序，另外，不同的人可能会选择不同的城市作为着色的起点，而当时的程序没有考虑这个问题。于是，把程序修改为下面的样子，还请同行分析并指出代码中的不足之处：
＃i nclude <stdio.h>
#define N 21
int allcolor[4]/*可用的颜色*/
int ok(int metro[N][N],int r_color[N],int current)
{/*ok函数和下面的go函数和原来的一样,保留用来比较两种算法*/
int j
for(j=1j<currentj++)
if(metro[current][j]==1&&r_color[j]==r_color[current])
return 0
return 1
}
void go(int metro[N][N],int r_color[N],int sum,int current)
{
int i
if(current<=sum)
for(i=1i<=4i++)
{
r_color[current]=i
if(ok(metro,r_color,current))
{
go(metro,r_color,sum,current+1)
return
}
}
}
void color(int metro[N][N],int r_color[N],int sum,int start)
{
int i,j,k
r_color[start]=allcolor[0]
for(i=start+1i!=starti=(i+1)%(sum+1))/*把所有编号看作一个环*/
if(i==0)/*城市号从1开始编号,故跳过0编号*/
continue
else
for(j=0j<4j++)
{
r_color[i]=allcolor[j]/*选取下一种颜色,根据allcolor中颜色顺序不同，结果不同*/
for(k=1k<ik++)/*检查是否有冲突，感觉还可以改进，如使用禁忌搜索法*/
if(metro[i][k]==1&&r_color[k]==r_color[i])
break
if(k>=i)
break
}
}
void main()
{
int r_color[N]={0}
int t_color[N]={0}
int i
int start/*着色的起点*/
int metro[N][N]={{0},
{0,1,1,1,1,1,1},
{0,1,1,1,1},
{0,1,1,1,0,0,1},
{0,1,1,0,1,1},
{0,1,0,0,1,1,1,0,0,1,0,0,0,0,0,0,1},
{0,1,0,1,0,1,1,1,1,1},
{0,0,0,0,0,0,1,1,1},
{0,0,0,0,0,0,1,1,1,1,0,0,1},
{0,0,0,0,0,1,1,0,1,1,0,0,1,1,1,0,1},
{0,0,0,0,0,0,0,0,0,0,1,1,0,1,0,1,0,0,0,1},
{0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1},
{0,0,0,0,0,0,0,0,1,1,0,1,1,1,0,0,0,0,0,1,1},
{0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,1,0,0,0,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,1,1,1,0,1},
{0,0,0,0,1,0,0,0,1,0,0,0,0,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1},
{0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,1,0,0,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1}}
allcolor[0]=1allcolor[1]=2allcolor[2]=3allcolor[3]=4/*选色顺序，顺序不同，结果不同*/
start=1
/* clrscr()*/
printf("\nAll color is:\n")
for(i=0i<4i++)/*当前选色顺序*/
printf("%d",allcolor[i])
go(metro,r_color,20,1)
printf("\nFirst method:\n")
for(i=1i<=20i++)
printf("%3d",r_color[i])
color(metro,t_color,20,start)
printf("\nSecond method:\n")
printf("\nAnd the start metro is:%d\n",start)
for(i=1i<=20i++)
printf("%3d",t_color[i])
}
说是人性化着色，其实还有一个问题没有考虑，那就是操作员跳跃式着色，就像大家玩“扫雷”游戏一样。其实也容易实现，可以像定义选色顺序一样定义着色顺序。
