随笔 - 147  文章 - 71  trackbacks - 0
<2024年11月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

常用链接

留言簿(1)

随笔分类(146)

随笔档案(147)

文章分类(28)

文章档案(28)

喜欢的Blog

搜索

  •  

最新评论

阅读排行榜

评论排行榜

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<&& tag;i++){
            
for(j=i+1;j<&& 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<&& 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 飞翔天使 阅读(852) 评论(1)  编辑  收藏 所属分类: poj

FeedBack:
# re: poj1129(Channel Allocation) 2012-05-09 15:36 11
DFS(x,1,cnum,n)//应该这样吧?  回复  更多评论
  

只有注册用户登录后才能发表评论。


网站导航: