题目翻译:
当一个广播电台在一个非常大的地区,广播站会用中继器来转播信号以使得每一个接收器都能接收到一个强烈的信号。然而,每个中继器必须慎重选择使用,使相邻的中继器不互相干扰。如果相邻的中继器使用不同的频道,那么就不会相互干扰。
由于无线电频道是一有限的,一个给定的网络所需的中继频道数目应减至最低。编写一个程序,读取一个中继网络,然后求出需要的最低的不同频道数。
解题思路:就是搜索每一行的数,找到所需颜色组多的次数,如果有冲突就在原来的基础上+1,如果没有就不管了。
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 10944 | Accepted: 5622 |
Description
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
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
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.
#include <stdio.h> #include <string.h> #include <iostream> using namespace std; int main() { int dp[120], v[120]; int i, j, n, k, t, p = 1; char s[120]; while(~scanf("%d",&n) && n) { memset(dp , 0 , sizeof(dp)); cin >>s; dp[0] = 1; t = 1; for(i = 1; i < n; i++) { cin >>s; k = strlen(s); if(k == 2) { dp[i+'A'] = 1; continue; } memset(v , 0 , sizeof(v)); for(j = 2; j < k; j++) { if(dp[s[j]-'A']) v[dp[s[j]-'A']] = 1;//出现过的次数 } for(j = 1; j < 27; j++) { if(!v[j]) { p = j; break; } } if(t < p) t = p; dp[i] = p; } if(t == 1) printf("1 channel needed.\n"); else printf("%d channels needed.\n",t); } return 0; }