解题思路
题意:
用中继器(repeater)给每个接受者(receiver)发送信号,为了防止信号干扰,两个相邻的广播站之间的中继器要不相同。问至少需要多少个中继器。
这个问题相当于给定—个图,如果要求把所有顶点涂上颜色,使得相邻顶点具有不同的颜色,问最少需要几种不同的颜色。经典的图着色问题。
思路:
根据给出的点构造邻接矩阵,顶点相邻的位置置1,不同的置0。因为图着色问题颜色最多是四种颜色。所以1种,2种,3种,4种,一个一个试,如果返回回来的着色方案总数不是0说明可行,为用的最少的颜色数。
关于图着色问题请参阅 -------等等再发
#include <stdio.h> #include <string.h> #include <ctype.h> #define N 27 int g[N][N], num, n; int x[N];
int ok(int t) { int i; for(i = 1; i<=n; i++) { if(i != t) { if(g[t][i] == 1 && x[i] == x[t]) return 0; } } return 1; }
void traceback(int t, int m) { int i; if(t > n) { num++; } else { for(i=1; i<=m; i++) { x[t] = i; if(ok(t)) traceback(t+1, m); x[t] = 0; } } }
int main() { int i, j; char ch; while(scanf("%d", &n) && n) { memset(g, 0, sizeof(g)); ch = getchar(); for(i=1; i<=n; i++) { ch = getchar(); ch = getchar(); while(isalpha(ch = getchar())) //输入这里要注意 { g[i][ch-'A'+1] = 1; g[ch-'A'+1][i] = 1; } } for(j=1; j<=4; j++) { num = 0; traceback(1, j); if(num != 0) { if(num == 1) printf("1 channel needed.\n"); //还有这里 else printf("%d channels needed.\n", j); break; } } } return 0; }
|
阅读(1143) | 评论(0) | 转发(0) |