不知道大家看到这行字没
Note that the adjacency is a symmetric relationship; if A is adjacent to B, then B is necessarily adjacent to A. Also, since the repeaters lie in a plane, the graph formed by connecting adjacent repeaters does not have any line segments that cross. 
由于是平面上的着色问题。所以最多只能着4种颜色（虽然4色问题没有严格的数学证明。但已被计算机穷举法证明），而要涂4种颜色的情况仅有图中出现k4完全图的情况。（k5在平面图上是不可能实现的，详细内容在离散数学上有证明）故只要枚举是否有k4，若无，枚举k3，若无，找相邻边，若无，则只需着一种颜色。程序如下。

#include<iostream.h>
#include<string.h>
int const maxn = 27;
int n;
bool map[maxn][maxn];
void init()
{
	memset(map,false,sizeof(map));
	int i;
	for (i=0; i<n; i++)
    {
    	char ch[200];
    	cin >> ch;
    	int j;
    	for (j=2; j<strlen(ch); j++)
    	  {
    	  	  map[ch[0]-'A'][ch[j]-'A'] = true;
    	  	  map[ch[j]-'A'][ch[0]-'A'] = true;
		  }
	}
}
void solve()
{
	int i,j,k,q;
	for (i=0; i<n; i++)
	 for (j=0; j<n; j++)
	  for (k=0; k<n; k++)
	   for (q=0; q<n; q++)
	     if (map[i][j]&&map[i][k]&&map[i][q]
	     &&map[j][k]&&map[j][q]&&map[k][q])
	       {
	       	  cout << "4 channels needed."<<endl;
	       	  return ;
		   }
    for (i=0; i<n; i++)
     for (j=0; j<n; j++)
      for (k=0; k<n; k++)
       if (map[i][j]&&map[i][k]&&map[j][k])
         {
         	cout << "3 channels needed."<<endl;
         	return ;
		 }
    for (i=0; i<n; i++)
     for (j=0; j<n; j++)
      if (map[i][j])
       {
       	  cout << "2 channels needed."<<endl;
       	  return ;
	   }
    cout << "1 channel needed."<<endl;
}
int main()
{
	while(cin>>n&&n)
	{
	init();
	solve();
	}
}

• Re:这个问题在平面图上是能通过多项式时间求解的 (44) qianbianwanjie 2009-04-14 16:12:36
  • 赞，顶色数!=最大团问题 (53) xuhanqiu 2009-06-05 21:43:37
    • 最大团就是=着色数吧 而且最大团本身也是NP 问题 (106) Snow_storm 2010-11-04 18:52:04
  • Re:这个问题在平面图上是能通过多项式时间求解的 (27) ly50247 2009-07-24 08:42:48
    • Re:人家说周围围了5个点，不是4个。。。 (0) alazyrabbit 2009-09-07 12:19:07