题目:http://poj.org/problem?id=1129
题意:
当一个广播电台在一个非常大的地区,广播站会用中继器来转播信号以使得每一个接收器都能接收到一个强烈的信号。然而,每个中继器必须慎重选择使用,使相邻的中继器不互相干扰。如果相邻的中继器使用不同的频道,那么就不会相互干扰。
由于无线电频道是一有限的,一个给定的网络所需的中继频道数目应减至最低。编写一个程序,读取一个中继网络,然后求出需要的最低的不同频道数。
View Code
1 #include2 #include 3 using namespace std; 4 struct node 5 { 6 int next[27];//后继 7 int num;//后继的个数 8 }point[27]; 9 int main()10 {11 int i,j,n;12 while(scanf("%d",&n)!=EOF)13 {14 if(n==0)15 break;16 getchar();17 for(i=1;i<=n;i++)18 {19 getchar();//节点序号20 getchar();//冒号21 char c;22 point[i].num=1;23 while(scanf("%c",&c),c!='\n')//输入序号的后继24 {25 int u;26 u=c-'A'+1;27 point[i].next[point[i].num]=u;28 point[i].num++;29 }30 }31 //从最小开始染色32 int color[27]={ 0};//标记第i个点染的最小颜色33 color[1]=1;34 int max=1;//最大染色数35 for(i=1;i<=n;i++)36 {37 color[i]=n+1;//假设染最大的颜色38 int vis[27]={ 0};//标记39 for(j=1;j j)47 {48 color[i]=j;//更新i节点的颜色,使之最小49 break;50 }51 }52 if(max