POJ - 1129 Channel Allocation解题报告（涂色问题+四色定理）

模型化好像就是涂颜色，相连的点不能涂一个颜色。告诉你了哪些点相连。对于每个点，枚举所有的颜色，如果这个颜色被它相邻的位置的点涂过了，那就换下一个颜色。

数据比较小，测试数据也很弱，然后就水过去了，也没有剪枝。

#include<iostream>
#include<stdio.h> 
#include<string.h>
#define N 30
#define inf 0x3f3f3f3f
using namespace std;

int color[N]={0};
int n;//n个点 
bool next[N][N]={0}; 
int best;

void dfs(int x)//给x号涂色 
{
	if(x==n+1)
	{
		int sum=0;
		/*for(int i=1;i<=n;i++)
		{
			cout<<color[i];
		}
		cout<<endl;*/
		int l[30]={0};
		for(int i=1;i<=n;i++)
		{
			if(l[color[i]]==0)
			{
				l[color[i]]=1;
				sum++;
				//cout<<sum;
			}
		}
		if(best>sum)best=sum;
		return;
	}
	for(int i=1;i<=best;i++)
	{
		bool flag=1;
		for(int j=1;j<=n;j++)
		{
			if(next[j][x]==1&&color[j]==i)
			{
				flag=0;
				break;
			}
		}
		if(flag==1)
		{
			color[x]=i;
			dfs(x+1);
			color[x]=0;
		}
	}
}

int main()
{
	while(cin>>n)
	{
		if(n==0)break;
		best=26;
		for(int i=1;i<=n;i++)
		{
			char l[N]={0};
			cin>>l;
			for(int j=2;j<strlen(l);j++)
			{
				next[i][(int)(l[j]-'A'+1)]=1;
			}
		}
		
		dfs(1);
		if(best==1)
		{
			cout<<"1 channel needed."<<endl;
		}
		else
		{
			cout<<best<<" channels needed."<<endl;
		}
		memset(color,0,sizeof(color));
		memset(next,0,sizeof(next));
	}
} 

然后是为什么这个题符合四色定则：

注意题中有这样一句话：“城市所在的世界是一个平面世界，当把城市看做点，相邻城市用边连接时，这些边不能相交”；

然后我觉得这个文章说的还不是很严谨的证明了题目所给模型符合四色定理。有时间要仔细想想怎么用很巧妙地描述证明。

附网址：http://blog.csdn.net/lyy289065406/article/details/6647986