http://acm.pku.edu.cn/JudgeOnline/problem?id=1129
【題意簡述】信道分配。給定一個無向圖，為每頂點填上顏色，要求滿足相鄰的頂點顏色不同，問最少的顏色數是多少?
【分析】利用四色定理，直接枚舉顏色數+DFS，其中DFS是暴力枚舉每個頂的顏色，以便找到一個可行解。
import java.util.*;
import java.io.*;
public class poj_1129
{
public static int[][] g=new int[26][26];
public static int solve(int n){
int i,j,cnum;
boolean tag=true;
// 無邊圖只用1色即可
for(i=0;i<n && tag;i++){
for(j=i+1;j<n && tag;j++){
if(g[i][j]==1)
tag=false;
}
}
if(tag)
return 1;
for(cnum=2;cnum<=4;cnum++) // 枚舉答案+dfs
{
int[] x=new int[n];
Arrays.fill(x,-1);
if(DFS(x,0,cnum,n))
return cnum;
}
return -1;
}
//DFS的復雜度是顏色數^頂點數(4^26，其中可行性剪枝剪掉了很多分支)
public static boolean DFS(int[] x,int vnum, int cnum,int n){
if(vnum == n) return true; // v的頂點都上色，可行解
for(int i=0;i<cnum;i++){ // 如果某個頂點沒有顏色填，返回上一層
x[vnum] = i;
if(check(vnum,x,i,n))
if(DFS(x,vnum+1,cnum,n)) // 合法，枚舉下一個頂點
return true;
}
return false;
}
// 判斷相鄰的頂點是否有涂過這種顏色
public static boolean check(int vnum,int[] x,int t,int n){
boolean find=true;
for(int i=0;i<n && find;i++){
if(g[vnum][i]==1 && x[i]==t)
find=false;
}
return find;
}
public static void main(String rgs[]) throws Exception
{
Scanner cin = new Scanner(new BufferedInputStream(System.in));
int i,j,n=cin.nextInt();
while(n!=0){
for(i=0;i<n;i++)
Arrays.fill(g[i],0);
for(i=0;i<n;i++){
String s = cin.next();
for(j=2;j<s.length();j++)
g[i][s.charAt(j)-'A']=1;
}
int count=solve(n);
if(count==1)
System.out.println(count+" channel needed.");
else
System.out.println(count+" channels needed.");
n=cin.nextInt();
}
}
}posted on 2009-09-10 15:21
飛翔天使 閱讀(866)
評論(1) 編輯 收藏 所屬分類:
poj