poj1129ChannelAllocation

在一个区域内有若干信号转发器,相邻的装发器不能转发相同频道的信号. 给你一个转发器的分布图.让你确定最少需要的频道数量

思路:图着色的问题.由于只有26个点.直接就过了.

//bnu1248
#include<iostream>
#include<stdio.h>
#include<string.h>

using namespace std;
#define MAX 30

int n;
int mmp[MAX][MAX];
int vis[MAX];
int col[5];//4中颜色
char inp[MAX][MAX];
int ans;
int init()
{
    int t,i,k;
    for(int j=0;j<n;j++)
    {
        t=inp[j][0]-'A';
        for(i=2;inp[j][i]!='\0';i++)
        {
            k=inp[j][i]-'A';
            mmp[t][k]=1;
            mmp[k][t]=1;
        }
    }
    return 0;
}
int work()
{
    for(int j=0;j<n;j++)
    {
        memset(col,0,sizeof(col));
        for(int i=0;i<n;i++)
        {
            if(mmp[j][i])
                col[vis[i]]=1;
        }
        for(int i=1;i<=4;i++)
        {
            if(!col[i])
            {
                vis[j]=i;
                ans=ans>i?ans:i;
                break;
            }
        }
    }
    return 0;
}
int main()
{
    while(scanf("%d",&n) && n)
    {
        memset(mmp,0,sizeof(mmp));
        memset(vis,0,sizeof(vis));
        for(int i=0;i<n;i++)
            scanf("%s",inp[i]);
        init();
        ans=0;
        work();
        if(ans==1)
            printf("1 channel needed.\n");
        else
            printf("%d channels needed.\n",ans);
    }
    return 0;
}