轉(zhuǎn)載于：…(*￣０￣)ノ

Channel Allocation

Description

When a radio station is broadcasting over a very large area, repeaters are used to retransmit the signal so that every receiver has a strong signal. However, the channels used by each repeater must be carefully chosen so that nearby 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

The input consists of a number of maps of repeater networks. Each map begins with a line containing the number of repeaters. This is between 1 and 26, and the repeaters are referred to by consecutive upper-case letters of the alphabet 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

For each map (except the final one with no repeaters), print a line containing the minumum number of channels needed so that no adjacent channels interfere. The sample output shows the format of this line. Take care that channels 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.

題意： 當(dāng)一個(gè)廣播電臺在一個(gè)非常大的地區(qū)，廣播站會用中繼器來轉(zhuǎn)播信號以使得每一個(gè)接收器都能接收到一個(gè)強(qiáng)烈的信號。然而，每個(gè)中繼器必須慎重選擇使用，使相鄰的中繼器不互相干擾。如果相鄰的中繼器使用不同的頻道，那么就不會相互干擾。

由于無線電頻道是一有限的，一個(gè)給定的網(wǎng)絡(luò)所需的中繼頻道數(shù)目應(yīng)減至最低。編寫一個(gè)程序，讀取一個(gè)中繼網(wǎng)絡(luò)，然后求出需要的最低的不同頻道數(shù)。

給出一些點(diǎn)以及這些點(diǎn)直接的連接關(guān)系，求最少可以用幾種顏色對這些點(diǎn)涂色，使得相鄰的點(diǎn)的顏色不同

解題思路：

對于這題數(shù)據(jù)范圍很小（節(jié)點(diǎn)最多26個(gè)），所以使用普通的暴力搜索法即可

對點(diǎn)i的染色操作：從最小的顏色開始搜索，當(dāng)i的直接相鄰（直接后繼）結(jié)點(diǎn)已經(jīng)染過該種顏色時(shí)，搜索下一種顏色。

就是說i的染色，當(dāng)且僅當(dāng)i的臨近結(jié)點(diǎn)都沒有染過該種顏色，且該種顏色要盡可能小。

要注意題中的一句話

since the repeaters lie in a plane, the graph formed byconnecting adjacent repeaters does not have any line segments that cross.

大致意思就是 “城市所在的世界是一個(gè)平面世界，當(dāng)把城市看做點(diǎn)，相鄰城市用邊連接時(shí)，這些邊不能相交”

?

PS： 在網(wǎng)上很多同學(xué)都說用“四色定理”解決這題， 其實(shí)不是，四色定理在本題單純是用來剪枝的，而且由于結(jié)點(diǎn)數(shù)較少（只有26），剪枝與否對時(shí)間影響不大，普通的爆搜也是0ms AC的，不過有興趣的同學(xué)可以看看“四色定理”。

因?yàn)楫?dāng)結(jié)點(diǎn)數(shù)很多時(shí)，四色定理的剪枝優(yōu)勢就會體現(xiàn)出來了

?

我把 暴力搜索 和 經(jīng)過四色定理剪枝的搜索 兩個(gè)程序都都貼出來，大家比較一下就知道四色定理怎么用了。

?

附：

四色定理的“相鄰”是指兩塊多邊形地區(qū)“至少一條邊重合”才為之相鄰

“至少一條邊重合”同時(shí)也隱含了“任意邊（線段）不正規(guī)相交

如：

我舉一個(gè)例子就一目了然了：

N=7

A:BCDEFG

B:ACDEFG

C:ABD

D:ABCE

E:ABDF

F:ABEG

G:ABF

畫成圖就是：

PS:由于邊不允許相交，這已經(jīng)是7個(gè)點(diǎn)的最大連接數(shù)

四色定理的原始理論依據(jù)：

對于一個(gè)散點(diǎn)集，若要求盡可能連接任意兩個(gè)點(diǎn)，但任意一條邊邊不允許與其他邊相交，

那么當(dāng)散點(diǎn)集的元素個(gè)數(shù)<=4時(shí)，連接所得的圖必為一個(gè)一個(gè) 無向完全圖

當(dāng)散點(diǎn)集的元素個(gè)數(shù)>4時(shí)，連接所得的圖必不是一個(gè)完全圖

完全圖：任意兩點(diǎn)均相鄰

?

最后千萬要注意輸出，當(dāng)頻道數(shù)大于1時(shí)，channel為復(fù)數(shù) channels

/*四色定理*///Memory Time //184K 0MS #include<iostream> using namespace std;typedef class {public:int next[27]; //直接后繼int pn; //next[]指針（后繼個(gè)數(shù)） }point;int main(int i,int j,int k) {int n;while(cin>>n){if(!n)break;getchar(); //n的換行符point* node=new point[n+1]; //結(jié)點(diǎn)/*Structure the Map*/for(i=1;i<=n;i++){getchar(); //結(jié)點(diǎn)序號getchar(); //冒號if(node[i].pn<0) //初始化指針node[i].pn=0;char ch;while((ch=getchar())!='\n'){j=ch%('A'-1); //把結(jié)點(diǎn)字母轉(zhuǎn)換為相應(yīng)的數(shù)字，如A->1 C->3node[i].next[ ++node[i].pn ]=j;}}int color[27]={0}; //color[i]為第i個(gè)結(jié)點(diǎn)當(dāng)前染的顏色，0為無色（無染色）color[1]=1; //結(jié)點(diǎn)A初始化染第1種色int maxcolor=1; //當(dāng)前已使用不同顏色的種數(shù)for(i=1;i<=n;i++) //枚舉每個(gè)頂點(diǎn){color[i]=n+1; //先假設(shè)結(jié)點(diǎn)i染最大的顏色bool vist[27]={false}; //標(biāo)記第i種顏色是否在當(dāng)前結(jié)點(diǎn)的相鄰結(jié)點(diǎn)染過for(j=1;j<=node[i].pn;j++) //枚舉頂點(diǎn)i的所有后繼{int k=node[i].next[j];if(color[k]) //頂點(diǎn)i的第j個(gè)直接后繼已染色vist[ color[k] ]=true; //標(biāo)記該種顏色}for(j=1;i<=n;j++) //從最小的顏色開始，枚舉每種顏色if(!vist[j] && color[i]>j) //注意染色的過程是一個(gè)不斷調(diào)整的過程，可能會暫時(shí)出現(xiàn)大于4的顏色{ //因此不能單純枚舉4種色，不然會WAcolor[i]=j;break;}if(maxcolor<color[i]){maxcolor=color[i];if(maxcolor==4) //由四色定理知，最終完成染色后，圖上最多只有四種顏色break; //因此當(dāng)染色過程出現(xiàn)結(jié)點(diǎn)的顏色為4時(shí)，就可以斷定最少要用4種顏色染色}}if(maxcolor==1)cout<<1<<" channel needed."<<endl;elsecout<<maxcolor<<" channels needed."<<endl;delete node;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的poj 1129 Channel Allocation——四色定理的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。