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.
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.
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 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 using namespace std; 5 int N; 6 bool num[30][30]; 7 int flag[30]; 8 int minS; 9 bool mark; 10 bool judge(int x,int value) 11 { 12 int i; 13 for(i=1;i<=N;i++) 14 { 15 if( num[x][i] && flag[i]==value && i!=x) 16 { 17 return false; 18 } 19 } 20 return true; 21 } 22 23 void dfs(int step) 24 { 25 if(step==N+1) 26 { 27 int k; 28 int mm=0; 29 for(k=1;k<=N;k++) 30 { 31 if(flag[k]>mm) 32 { 33 mm=flag[k]; 34 } 35 } 36 minS=mm; 37 mark=true; 38 return; 39 } 40 if(mark) 41 { 42 return; 43 } 44 int i; 45 for(i=1;i<=N;i++) 46 { 47 flag[step]=i; 48 if(!judge(step,i)) 49 { 50 flag[step]=0; 51 continue; 52 } 53 dfs(step+1); 54 if(mark) 55 return; 56 flag[step]=0; 57 } 58 } 59 int main() 60 { 61 while(~scanf("%d",&N) && N ) 62 { 63 char str[50]; 64 int i,j; 65 memset(num,false,sizeof(num)); 66 for(i=0;i<N;i++) 67 { 68 scanf("%s",str); 69 for(j=2;str[j]!='\0';j++) 70 { 71 int a=str[j]-'A'+1; 72 num[i+1][a]=true; 73 } 74 } 75 memset(flag,0,sizeof(flag)); 76 flag[1]=1; 77 mark=false; 78 dfs(2); 79 if(minS==1) 80 { 81 printf("%d channel needed.\n",minS); 82 } 83 else 84 { 85 printf("%d channels needed.\n",minS); 86 } 87 88 } 89 return 0; 90 }
此题DFS。
题目意思是说给你N个点，点与点之间存在联系。
具体关系是：
假设A与B有关系，那么点A上的权值必须和B上的不一样。问至少有多少个权值。
样例解释。
样例1：因为A与B没有关系，所以，Ａ的权值是１，那么Ｂ的权值也是１，也就是说只需要一个；
样例２：因为Ａ与Ｂ，Ｃ存在关系，那么A的权值如果为1，那么B的就不能是1，就是2了，因为C与A、B都存在关系，那么C的权值不能是1、2了，那么就是3了，
而D与B、C存在关系，就是说D的权值不能是2或者3了，因为D与A没有关系，也就是说D的权值可以是1（尽量让权值小），那么总的来说，最少要用三个channels；
样例3与样例2相似，就不作具体解释。
解题思路：
根据深搜的思想。再加上做数独的思想，来解这道题。
相当于刚开始就只有A需要一个，即另A的权值为1，即flag[1]=1;
然后填第二个数字，也就是B的权值，判断B这一点的约束条件，如果不符合条件，就换一个权值试一下；
举例说明一下：
样例2：
首先flag[1]=1,代表现把1这个数字填进去，然后填2的时候先把1填到第二个位置，判断一下是否符合条件，因为根据样例2，节点Ａ与Ｂ是有关系的，代表他们的权值不能相等，即填１到第二个位置是不行的，那么就填２到第二个位置，看看时候满足条件，以此类推下去，当把Ｎ个点都填完了，往flag[]数组里面找最大的权值，也就是题目要求的最小的channels。