OpenJudge NOI 2.5 131:Channel Allocation

【题目链接】

OpenJudge NOI 2.5 131:Channel Allocation

【题目翻译】

信道分配

描述

当一个无线电站在为一个很大的区域广播时，为了让接受者接收到强信号，会使用中继器来重新发送信号。然而，为了距离近的中继器之间互不影响，必须仔细选择每个中继器使用的信道。只要临近的中继器使用不同的信道，这样的情况就是令人满意的。

因为无线电频谱是宝贵的资源，一个给定中继器网络所需要的信道数量应该尽量少。你必须写一个程序，读入对中继器网络的描述，而后确定最少信道数量。

输入：

输入由很多中继器网络的地图组成。每个地图的第一行是中继器的数量，在1到26之间。中继器由连续的以A为起始的大写字母表示。例如，10个中继器会有名字A,B,C,…,I和J。一个有0个中继器的网络表示输入结束。
在中继器数量后是一个表示邻接关系的列表。每行的格式是：
A:BCDH
表示了中继器B,C,D和H与中继器A邻接。第一行描述了邻接中继器A的中继器，第二行描述了邻接B的，依次类推直到所有的中继器。如果一个中继器不与任何其他中继器相邻，这一行的格式为：
A:
中继器以字母表顺序列出
注意邻接关系是一种对称的关系。如果A与B邻接，那么B一定与A邻接。而且，因为中继器都在一个平面中，连接相邻中继器形成的图不存在任何交叉的线段。

输出：

对于每个地图（除了最后一个没有中继器的地图），打印使得相邻频道互不干扰所需的最少频道。输出样例展示了这一行的格式。注意当只需要1个信道时，信道这个词是单数形式。

样例输入

2
A:
B:
4
A:BC
B:ACD
C:ABD
D:BC
4
A:BCD
B:ACD
C:ABD
D:ABC
0

样例输出

1 channel needed.
3 channels needed.
4 channels needed.

来源

Southern African 2001

【题目考点】

1. 图论：最小着色问题

解决方法：深搜回溯

【解题思路】

中继器是顶点，相连关系是边，建立无向图。中继器的频道相当于顶点的颜色。
对图中每个顶点进行着色，要求相邻顶点的着色不同，该问题为无向图中的最少着色问题。
使用color数组记录每个顶点的着色，如果color[i]为0，表示尚未着色。
设当前已使用着色数为c n cncn
当访问到一个顶点时，尝试对该顶点进行着色，分别尝试颜色1到颜色c n cncn。
在尝试着色颜色c cc时

• 如果当前顶点有颜色为c cc的邻接点，那么当前顶点不能着色为c cc。
• 如果当前顶点的邻接点的颜色都不为c cc，那么当前顶点可以着色为c cc，接下来继续确定下一个顶点的颜色。

在尝试了颜色1到颜色cn后，还要再尝试将当前顶点着色为颜色c n + 1 cn+1cn+1，将总使用颜色数量增加1，继续进行搜索。

剪枝：

1. 按度从大到小的顺序依次确定每个顶点的着色，这样会让更多的顶点受到邻接点已有着色的限制，减少搜索的规模（优化搜索顺序）
   这一步可以设顶点的索引数组d dd，d[i]表示所有顶点按照度从大到小排序后第i ii个顶点的编号。
   按照d dd数组中存储的顶点顺序依次确定每个顶点的颜色。
2. a n s ansans为已经搜索到的所有方案中，着色数最少的方案的着色数量。如果当前已经尝试颜色数量c n ≥ a n s cn\ge anscn≥ans，则不需要再进行搜索了。（最优性剪枝）

搜索结束后，a n s ansans为当前图的最少着色数。
按照要求输出结果语句，注意a n s = 1 ans=1ans=1时，channel这个单词为单数channel。当a n s > 1 ans>1ans>1时，channel这个单词为复数channels。

特殊地，题目限定了了给定的图是平面图，平面图满足四色定理，即图的最少着色数小于等于4。因此本题的结果一定小于等于4。

【题解代码】

解法1：求图的最少着色数

#include<bits/stdc++.h>usingnamespacestd;#defineN30intn,ans,color[N],deg[N],d[N],edge[N][N];boolcmp(inta,intb){returndeg[a]>deg[b];}boolcheck(intu,intc)//顶点u的邻接点是否存在颜色c{for(intv=0;v<n;++v)if(edge[u][v]&&color[v]==c)returnfalse;returntrue;}voiddfs(intdi,intcn){if(cn>=ans)return;if(di==n){ans=cn;return;}intu=d[di];for(intc=1;c<=cn;++c)if(check(u,c)){color[u]=c;dfs(di+1,cn);}color[u]=cn+1;dfs(di+1,cn+1);color[u]=0;}intmain(){charc;string s;while(cin>>n&&n!=0){cin.get();//读掉换行符ans=1e9;memset(edge,0,sizeof(edge));memset(color,0,sizeof(color));memset(deg,0,sizeof(deg));for(inti=1;i<=n;++i){intu=cin.get()-'A';//读入起始顶点字符cin.get();//读掉冒号while((c=cin.get())&&c!='\n'){intv=c-'A';edge[u][v]=edge[v][u]=1;//为了去除重边，使用邻接矩阵deg[u]++,deg[v]++;}}for(inti=0;i<n;++i)d[i]=i;sort(d,d+n,cmp);dfs(0,0);if(ans==1)cout<<ans<<" channel needed.\n";elsecout<<ans<<" channels needed.\n";}return0;}