POJ 1129 | 频道分配（图的着色）
频道分配（Channel Allocation）
题目来源：
South Africa 2001, ZOJ1084, POJ1129
题目描述：
当一个广播站向一个很广的地区广播时需要使用中继器，用来转发信号，使得接收器都能接收到足够强的信号。然而，每个中继器所使用的频道必须很好地选择，以保证相邻的中继器不会互相干扰。要满足这个条件，相邻中继器必须使用不同的频道。
由于广播频率带宽是一种很宝贵的资源，对于一个给定的中继器网络，所使用频道数量应该尽可能少。编写程序，读入中继器网络的信息，计算需要使用频道的最少数目。
输入描述：
输入文件中包含多个测试数据，每个测试数据描述了一个中继器网络。每个中继器网络的格式如下。
- 第1行为一个整数N，表示中继器的数目，1≤N≤26，中继器用前N个大写字母表示，例如，假设有10个中继器，则这10个中继器的名字为A，B，C，…，I和J。
- 接下来有N行，描述了这N个中继器的相邻关系，第1行描述和中继器A相邻的中继器，第2行描述和中继器B相邻的中继器；等等。每行的格式为：
A:BCDH表示和中继器A相邻的中继器有B、C、D和H（按字母升序排列）。如果一个中继器没有相邻中继器，则其格式为：
A:注意：相邻关系是对称的，A与B相邻，则B也与A相邻；另外，中继器网络是一个平面图，即中继器网络所构成的图中不存在相交的边。
输入文件最后一行为N＝0，表示输入结束。
输出描述：
对每个中继器网络，输出一行，为该中继器网络所需频道的最小数目。
分析：
很明显，本题要求的是图G的色数χ（G）。样例输入中第2个测试数据所描述的中继器网络如图20所示。本题采用前面介绍的顺序着色算法求解，例如在图20（c）中给顶点C着色时，它的邻接顶点中，顶点D和F目前没有着色，顶点B着色为第1种颜色，所以给顶点C着色为第0种颜色。最终的着色方案如图20（d）所示，求得的χ（G）为4。
代码如下：
要点说明：
1、计算最大节点，不用遍历26个字母
2、负数取反只有-1会为0
3、二维数组表示图
#include <stdio.h>;
#include <stdlib.h>
char buf[30];
int v[26], adj[26];
int m[26][26];
int main() {
int n, t, k, i, j;
int max;
freopen("test.txt", "r", stdin);
while (scanf("%d", &n) && n) {
memset(m, 0, sizeof(m));
memset(v, -1, sizeof(v));
t = n;
int maxc = 0;
while (t--) {
//输入字符串
scanf("%s", buf);
//记录第一个字符的ID
i = buf[0] - 'A';
maxc = i > maxc ? i:maxc;
for (k = 2; buf[k]; k++) {
//从第三个字符开始
j = buf[k] - 'A';
maxc = j > maxc ? j:maxc;
//连接这两个ID，数组形式
m[i][j] = m[j][i] = 1;
}
}
maxc = maxc + 1;
max = 0;
//二维数组的遍历
for (i = 0; i < maxc; i++) {
memset(adj, 0, sizeof(adj));
//如果存在连接，就置1
for (j = 0; j < maxc; j++) {
//注意这里-1取反为0，其他数字取反不为0
if (m[i][j] && ~v[j]) {
printf("v[j] %d\n", v[j]);
adj[v[j]] = 1;
}
}
for (j = 0; j < maxc; j++) {
if (!adj[j]) {
adj[j] = 1;
//注意这里是i,也就是设置当前节点的颜色
v[i] = j;
printf("节点%d 颜色%d\n", i, j);
//更新颜色数量
if (j > max)
max = j;
break;
}
}
}
printf("%d channel%s needed.\n", max + 1, max > 1 ? "s" : "");
}
return 0;
}本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-04-08，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读