Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 12312 | Accepted: 6297 |
Description
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
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
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.
Source
这题不知道四色定理就呵呵了,给个链接吧
点击打开链接
知道以后,爆搜!!!,颜色从少到多一个个试过去,只要某个方案可以成立就行
注意输出的时候分单复数
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; struct node { int to; int next; }edge[26 * 26]; int head[30]; int col[30]; int tot; int n; int num;// the number of the way void addedge(int from, int to) { edge[tot].to = to; edge[tot].next = head[from]; head[from] = tot ++; } bool is_legal(int u)// if the current color is legal { int v; for(int i = head[u]; i!=-1; i = edge[i].next) { v = edge[i].to; if(col[u] == col[v]) return false; } return true; } void dfs(int u, int cur_color) { if(u > n) { num ++; return ; } for(int i = 1;i <= cur_color; i ++) { col[u] = i; //the node's color is i if( is_legal(u) ) dfs(u + 1, cur_color); col[u] = 0; } } int main() { while(~scanf("%d", &n)) { if(!n) break; memset( head, -1, sizeof(head) ); tot = 0; char rept; int i; getchar(); for(i = 1;i <= n; i ++) { rept = getchar(); getchar(); while( rept = getchar() ) { if(rept == '\n') break; else if(rept == ':') continue; addedge(i, rept - 'A' + 1); addedge(rept - 'A' + 1, i); } } for(i = 1;i <= 4; i ++) { num = 0; memset( col, 0, sizeof(col) ); dfs(1, i); if(num) break; } if(i == 1) printf("1 channel needed.\n"); else printf("%d channels needed.\n", i); } return 0; }