m-最优着色问题。

 

我比较的菜做法是枚举了1~m然后得到答案的。

 

 

#include <iostream>
#include <string>
using namespace std;
int a[27][27];
int x[27];
int n;
void Next(int k,int m)
{
 do
 {
  int j;
  x[k]=(x[k]+1)%(m+1);
  if(!x[k]) return ;
  for( j=1;j<k;j++)
  {
   if(a[k][j]&&x[k]==x[j])
    break;
  }
  if(j==k) return ;
 }while(1);
}
int col(int k,int m)
{
 do
 {
  Next(k,m);
  if(!x[k]) return -1;
  if(k==n)
  {
   int temp=0;
   for(int i=1;i&lt;=n;i++)
   {
    temp=temp>x[i]?temp:x[i];
   }
   return temp;
  }
  else
   return col(k+1,m);
 }while(1);
}
int main()
{
 while(cin &gt;&gt;n&&n!=0)
 {
  string b;
  memset(a,0,sizeof(a));
  memset(x,0,sizeof(x));
  for(int i=0;i<n;i++)
  {
   cin >&gt;b;
   for(int j=2;j<b.size();j++)
   {
    a[b[0]-64][b[j]-64]=1;
   }
   b.erase();
  }
  for(int k=2;k&lt;=n;k++)
  {
   int ans=col(1,k);
       if(ans==1)
    {
        cout&lt;&lt;"1 channel needed."&lt;&lt;endl;
     break;
    }
    else if(ans>1)
    {
     cout&lt;&lt;ans&lt;&lt;" channels needed."&lt;&lt;endl;
     break;
    }
  }
 }
 return 0;

}