原题
Description
When a radio station is broadcasting over a very large area, repeaters are used to retransmit the signal so that every receiver has a strong signal. However, the channels used by each repeater must be carefully chosen so that nearby repeaters do not interfere with one another. This condition is satisfied if adjacent repeaters use different channels.
Since the radio frequency spectrum is a precious resource, the number of channels required by a given network of repeaters should be minimised. You have to write a program that reads in a description of a repeater network and determines the minimum number of channels required.
Input
The input consists of a number of maps of repeater networks. Each map begins with a line containing the number of repeaters. This is between 1 and 26, and the repeaters are referred to by consecutive upper-case letters of the alphabet starting with A. For example, ten repeaters would have the names A,B,C,…,I and J. A network with zero repeaters indicates the end of input.
Following the number of repeaters is a list of adjacency relationships. Each line has the form:
A:BCDH
which indicates that the repeaters B, C, D and H are adjacent to the repeater A. The first line describes those adjacent to repeater A, the second those adjacent to B, and so on for all of the repeaters. If a repeater is not adjacent to any other, its line has the form
A:
The repeaters are listed in alphabetical order.
Note that the adjacency is a symmetric relationship; if A is adjacent to B, then B is necessarily adjacent to A. Also, since the repeaters lie in a plane, the graph formed by connecting adjacent repeaters does not have any line segments that cross.
Output
For each map (except the final one with no repeaters), print a line containing the minumum number of channels needed so that no adjacent channels interfere. The sample output shows the format of this line. Take care that channels is in the singular form when only one channel is required.
Sample Input
2
A:
B:
4
A:BC
B:ACD
C:ABD
D:BC
4
A:BCD
B:ACD
C:ABD
D:ABC
0
Sample Output
1 channel needed.
3 channels needed.
4 channels needed.
原题大意
当无线电台在一个非常大的区域上传播信号时,为了每个接收器都能得到较强的信号,使用转发器转发信号.然而,需要仔细地选择每个转发器使用的频道,以使附近的转发器不彼此干扰.如果附近的转发器使用不同的频道,条件就得到满足.
因为无线电波的频道是宝贵的资源,转发器所需的频道数应减到最少.编程任务:读取转发器的信息,并计算所需频道的最小使用量.
输入格式
输入包含许多转发器的网络图.每幅图的第一行是转发器数目(1~26).转发器用连续的大写字母表示,从A开始.例如,10个转发器的名称是A,B,C,D……,I,J.当转发器的个数是0,表示输入结束.
转发器的数目之后,是其邻近关系的列表.每行的格式为A:BCDH
表示BCDH与A邻近.若某个转发器不与其他转发器邻近,它的形式为
A:
转发器按字母顺序列出(注意:相邻是对称的,A与B相邻同时B与A也相邻).
输出格式
对于每幅图(除了最后一个没有转发器),输出一行,是转发器不互相干扰所需的最小频道数.
算法分析
将本题抽象成无向图
样例分析
转发器A,B,C各不一样,A和D一样,所以需要3个转发器.
转发器A,B,C,D各不一样,所以需要4个转发器.构造无向图
用数组g保存图,表示两点间是否关联bool g[26][26];转发器的数量
int n;着色的实现
因为颜色不超过4种,所以分两种情况:- 所有转发器互不相邻,只要着一种色;
用两种或三种颜色去着色,如果不能成功就是需要4种颜色.
使用dfs()实现算法:bool dfs(int id,int color)id是着色的起点,color是限制的颜色数量.
当某一结点id时,在已经着色的结点中,搜索是否该颜色已经被使用.如果是,就换种颜色,继续搜索.
当所有的着色完成,返回true,否则返回false.
程序代码
#include <stdio.h>
#include <memory.h>
bool g[30][30];//无向图的存储
int used[30]; //每个点所用的颜色的存储
int n;//转发器的数量
bool dfs(int id,int color)//m为当前的点
{
bool flag;
int i,j;
for(i=0;i<color;i++)
{
flag=true;
//结点颜色
used[id]=i;
//判断相邻是否用同一种颜色
for(j=0;j<id;j++)
{
if(g[id][j]&&used[id]==used[j])//是否相邻,若相邻是否颜色相同
{
flag=false;
break;
}
}
if(flag&&(id==n||dfs(id+1,color)))
return true;
}
return false;
}
int main()
{
int i,j;
bool one;//只需要一种颜色的标记
char adj[60];
while(scanf("%d",&n)&&n)
{
one=true;
memset(g,0,sizeof(g));
memset(used,0,sizeof(used));
for(i=0;i<n;i++)
{
scanf("%s",adj);
for(j=2;adj[j];j++,one=false)
{
g[adj[j]-'A'][i]=true;//对称存储
g[i][adj[j]-'A']=true;
}
}
if(one) printf("1 channel needed.\n");
else if(dfs(1,2)) printf("2 channels needed.\n");
else if(dfs(1,3)) printf("3 channels needed.\n");
else printf("4 channels needed.\n");
}
return 0;
}