遂宁市城市建设档案馆网站杭州网站建设及推广

遂宁市城市建设档案馆网站,杭州网站建设及推广,php做网站的技术难点,百度关键词优化费用【题目链接】 OpenJudge NOI 2.5 131:Channel Allocation 【题目翻译】 信道分配 描述 当一个无线电站在为一个很大的区域广播时#xff0c;为了让接受者接收到强信号#xff0c;会使用中继器来重新发送信号。然而#xff0c;为了距离近的中继器之间互不影响#xff0…【题目链接】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个信道时信道这个词是单数形式。样例输入2A:B:4A:BCB:ACDC:ABDD:BC4A:BCDB:ACDC:ABDD:ABC0样例输出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 cn1cn1将总使用颜色数量增加1继续进行搜索。剪枝按度从大到小的顺序依次确定每个顶点的着色这样会让更多的顶点受到邻接点已有着色的限制减少搜索的规模优化搜索顺序这一步可以设顶点的索引数组d ddd[i]表示所有顶点按照度从大到小排序后第i ii个顶点的编号。按照d dd数组中存储的顶点顺序依次确定每个顶点的颜色。a n s ansans为已经搜索到的所有方案中着色数最少的方案的着色数量。如果当前已经尝试颜色数量c n ≥ a n s cn\ge anscn≥ans则不需要再进行搜索了。最优性剪枝搜索结束后a n s ansans为当前图的最少着色数。按照要求输出结果语句注意a n s 1 ans1ans1时channel这个单词为单数channel。当a n s 1 ans1ans1时channel这个单词为复数channels。特殊地题目限定了了给定的图是平面图平面图满足四色定理即图的最少着色数小于等于4。因此本题的结果一定小于等于4。【题解代码】解法1求图的最少着色数#includebits/stdc.husingnamespacestd;#defineN30intn,ans,color[N],deg[N],d[N],edge[N][N];boolcmp(inta,intb){returndeg[a]deg[b];}boolcheck(intu,intc)//顶点u的邻接点是否存在颜色c{for(intv0;vn;v)if(edge[u][v]color[v]c)returnfalse;returntrue;}voiddfs(intdi,intcn){if(cnans)return;if(din){anscn;return;}intud[di];for(intc1;ccn;c)if(check(u,c)){color[u]c;dfs(di1,cn);}color[u]cn1;dfs(di1,cn1);color[u]0;}intmain(){charc;string s;while(cinnn!0){cin.get();//读掉换行符ans1e9;memset(edge,0,sizeof(edge));memset(color,0,sizeof(color));memset(deg,0,sizeof(deg));for(inti1;in;i){intucin.get()-A;//读入起始顶点字符cin.get();//读掉冒号while((ccin.get())c!\n){intvc-A;edge[u][v]edge[v][u]1;//为了去除重边使用邻接矩阵deg[u],deg[v];}}for(inti0;in;i)d[i]i;sort(d,dn,cmp);dfs(0,0);if(ans1)coutans channel needed.\n;elsecoutans channels needed.\n;}return0;}