POJ1129 Channel Allocation DFS

放送局が放送するとき、聴衆に安定した新しい番号を受信させるために、一般的にはいくつかの中継器が新しい番号を再送します.新しい番号を強化する目的を達成します(各中継器は大文字の英字で表される).各中継器には1つの周波数帯域が必要であることが知られており、2つの中継器が隣接している場合、彼らが使用している周波数帯域は同じではありません.そうしないと、彼らは互いに信号の伝播を妨害します.今、ラジオ局の中継器間の隣接関係のネットワークを放送して、少なくともどれだけ使用する必要があるかを判断させます.異なる周波数帯域が少ない.
分析:放送局中継器間のネットワークは1つの図に対応しており、私たちは1からkで異なる周波数帯域を表し、0で1番目の中継器の周波数帯域を初期化し、その後、各中継器は、まず既存の周波数帯域で値を割り当て、関係ネットワークと矛盾しているかどうかを判断し、階層ごとに深く検索すればよい.
実装コードは次のとおりです.

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define INF 999999999
typedef struct node
{
    int to,next;
}EDGE;
EDGE edge[900];
int head[30];
int num;
int n,ans;
int co[30];
void add(int u,int v)
{
    edge[num].to=v;
    edge[num].next=head[u];
    head[u]=num++;
}
void init()
{
    char str[30];
    num=0;
    memset(head,-1,sizeof(head));
    for(int i=0;i<n;i++)
    {
        scanf("%s",str);
        int len=strlen(str);
        for(int j=2;j<len;j++)
        {
            add(i,str[j]-'A');
            add(str[j]-'A',i);
        }
    }
}
bool judge(int x)
{
    for(int i=head[x];i!=-1;i=edge[i].next)
      if(co[x]==co[ edge[i].to ]) return 0;
    return 1;
}
void dfs(int cnt,int x)
{
    if(x==n)
    {
        if(ans>cnt) ans=cnt;
        return ;
    }
    for(int i=0;i<cnt;i++)
    {
        co[x]=i;
        if(judge(x)) dfs(cnt,x+1);
    }
    co[x]=cnt;
    dfs(cnt+1,x+1);
}
int main()
{
    while(scanf("%d",&n)&&n)
    {
        init();
        ans=INF;
        memset(co,-1,sizeof(co));
        dfs(0,0);
        if(ans==1) puts("1 channel needed.");
        else printf("%d channels needed.
", ans);
    }
    return 0;
}