1129Channel Allocation

按A,B,C……的顺序搜索，让每个字母对应一个数，表示到这个字母时可以用的最少的频道，最后一个字母对应的最少的频道即要求的结果， 比如已经搜完了C,C对应的数是m， 轮到搜索D， D从1-m中选一种频道，如果这个频道和与D相关的字母的频道都不同，再往E搜， 如果不存在这样的频道，则D 用m种外的频道， D 对应的最少频道数即m+1。

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int a[30][30],b[30],n;
int small = 10000000;
void dfs(int nn,int mm)
{
    int i,j,k,g;
    k=0;
    if(nn==n+1)
    {
        if(small>mm)small=mm;
        return;
    }
    for(i=1;i<=mm;i++)
    {
        k=0;g=0;
        for(j=0;j<nn;j++)
        {
            if(a[nn][j])
            {
                g++;
                if(i!=b[j])k++;
            }
        }
        //cout<<"第i中颜色"<<i<<" "<<"第几个"<<nn<<" "<<g<<" "<<k<<endl;
        if(k==g)
        {
            b[nn]=i;
            dfs(nn+1,mm);
            b[nn]=0;
        }
        else
        {
            b[nn]=mm+1;
            dfs(nn+1,mm+1);
            b[nn]=0;
        }
    }
}
main()
{
    int i,j,k;
    char s[200];
    while(cin>>n)
    {
        if(n==0)break;
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        for(i=0;i<n;i++)
        {
            cin>>s;
            int len = strlen(s);
            k = s[0]-'A';

            for(j=2;j<len;j++)
            {
                a[k][s[j]-'A']=a[s[j]-'A'][k]=1;
            }


        }
        b[0]=1;
        small = 100000000;
        dfs(1,1);
        if(small==1)
        printf("1 channel needed.\n");
        else printf("%d channels needed.\n",small);

    }
}