pku1129 Channel Allocation

#include<stdio.h>

const int Maxn=26;
bool g[Maxn][Maxn];
int x[Maxn];
int n;

bool match(int pos)
{
    for(int i=0;i<pos;i++)
        if(g[pos][i]&&(x[pos]==x[i]))
            return false;
    return true;
}

void solve(int k)
{
    for(int i=0;i<n;i++)
        x[i]=0;

    int pos=0;
    while(pos>=0)
    {
        x[pos]++;
        while(x[pos]<=k&&!match(pos))
            x[pos]++;
        if(x[pos]<=k)
        {
            if(pos==n-1)    
                break;
            else
                pos++;
        }
        else
        {
            x[pos]=0;
            pos--;
        }
    }
}

int main()
{
    while(scanf("%d",&n),n)
    {
        getchar();
        char c;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                g[i][j]=false;
        for(int i=0;i<n;i++)
        {
            getchar();getchar();
            while((c=getchar())!='\n')
            {
                g[i][c-'A']=true;
            }
        }

        int k=0;
        do
        {
            k++;
            solve(k);
        }while(x[0]==0);

        if(k==1)
            printf("1 channel needed.\n");
        else
            printf("%d channels needed.\n",k);
    }
    return 0;
}

 

备注：

原本打算不限定总颜色数，但在无向图的遍历中存在访问的先后顺寻，导致后涂色的结点在先涂的不合理的结点的错误引导下涂色出错，比如（1-2-3-1，搜索顺序为第一点、第四点、第二点、第三点），因此还是设定颜色总数，在搜索的过程中不断调整，若达不到预定的颜色总数，则在回溯的过程中每个点都被清零，循环继续。