题目:http://poj.org/problem?id=1129

题意:求最小m,使平面图能染成m色,相邻两块不同色
由四色定理可知顶点最多需要4种颜色即可。我们于是从1开始试到3即可。

 #include <iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<stack>
#include<queue>
#include<iomanip>
#include<cmath>
#include<map>
#include<vector>
#include<algorithm>
using namespace std; int n,G[][],vis[][],ans;
void pri()
{
int f=-;
for(int i=; i<; i++)
{
for(int j=; j<n; j++)
if(vis[j][i]&&f<i)
f=i;
}
if(ans>f)
ans=f;
}
void dfs(int x)
{
if(x>=n)
{
pri();
return;
}
for(int i=; i<; i++)
{
int f=;
for(int j=; j<n; j++)
{
if((G[j][x]&&vis[j][i])||(G[x][j]&&vis[j][i]))
{
f=;
break;
}
}
if(f)
{
vis[x][i]=;
dfs(x+);
vis[x][i]=;
}
}
}
int main()
{
char s[];
while(cin>>n&&n)
{
memset(G,,sizeof(G));
memset(vis,,sizeof(vis));
for(int i=; i<n; i++)
{
cin>>s;
int u=s[]-;
for(int j=; s[j]; j++)
{
int v=s[j]-;
G[u][v]=;
}
}
ans=;
vis[][]=;
dfs();
ans+=;
if(ans == )
printf("1 channel needed.\n");
else
printf("%d channels needed.\n",ans);
}
return ;
}
05-08 15:11