POJ-1129-Channel Allocation-dfs探索+四色定理

タイトル翻訳:
放送局が非常に大きな地域にある場合、放送局は中継器で信号を中継し、各受信機が強い信号を受信できるようにする.しかしながら、各中継器は、隣接する中継器が互いに干渉しないように慎重に使用されなければならない.隣接する中継器が異なるチャンネルを使用する場合、互いに干渉しない.
無線チャネルは限られているため、所与のネットワークに必要な中継チャネルの数は最小限に抑えるべきである.プログラムを作成し、中継ネットワークを読み出し、必要な最低の異なるチャンネル数を求める.
地図を染める、、、NP-hard問題です.欲張りな方法では間違いだ...しかしpojのデータは比較的水で、混ぜることができます
欲張るとこんなデータに引っかかります

in

6

A:BEF
B:AC
C:BD
D:CEF
E:ADF
F:ADE

out

3 channels needed.



 ：A(1)B(2)C(3)D(1)E(2)F(3)

暴力dfs+四色定理剪定

#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>  
#include <stack>
#include <iostream>
using namespace std;   
double eps=1e6; 
int mp[30][30]; 
int vis[30]; 
int n,ok;
int minn;
int cnt=1;
void work(int x)
{	 
	if (x>n)
	{
		int i;
		int cun[5];
		for (i=1;i<=n;i++)
			cun[vis[i]]=1;
		int ans=0;
		for (i=1;i<=ok;i++)
			ans+=cun[i];	//      
		if (ans<minn)
			minn=ans;
		return ;
	} 
	if (vis[x]) return ;
	int i;
	int use[5];	//      ，  4     
	memset(use,0,sizeof(use)); 
	for (i=1;i<x;i++)
	{
		if (mp[x][i])
			use[vis[i]]=1;
		
	}
	for (i=1;i<=ok;i++)  //            
	{
		if (use[i]) continue;
		vis[x]=i;
		work(x+1);
		vis[x]=0;
	}
	if (ok==4) return ;		//      
	
	vis[x]=++ok;		//     
	work(x+1);
	vis[x]=0;
	ok--;
	
}

int main()
{
	int st,i,j,k;
	int t; 
	while(1)
	{
		ok=0;
		memset(mp,0,sizeof(mp));
		char tmp[105]; 
		cin>>n;
		if (!n)break;
		for (i=1;i<=n;i++)
		{ 
			scanf("%s",tmp);
			int len=strlen(tmp); 
			int x=tmp[0]-'A'+1;
			for (j=2;j<len;j++)
			{
				int v=tmp[j]-'A'+1;
				mp[x][v]=1;
			} 
		}
		minn=999l;
		memset(vis,0,sizeof(vis));
		work(1); 
		if (minn==1)
			printf("1 channel needed.
");
		else
			printf("%d channels needed.
",minn);
	}
	
	return 0;
}