1129 Channel Allocation

1129 Channel Allocation

問題

http://acm.pku.edu.cn/JudgeOnline/problem?id=1129

注意

隣接関係は対称的になっていると注釈がありますが，入力は必ずしもそうなっていません．AがBに隣接しているという入力があれば，BがAに隣接しているという情報を自分で補ってやる必要があります．

解答方針

平面グラフであるという注釈があるので，四色定理により必要なチャンネル数は4以下になることを利用します．

解答例

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(true){
            int n = sc.nextInt();
            if(n==0) break;
            
            boolean[][] adj = new boolean[n][n];
            for(int i=0;i<n;i++) Arrays.fill(adj[i],false);
            
            for(int i=0;i<n;i++){
                String line = sc.next();
                for(int j=2;j<line.length();j++){
                    int c = line.charAt(j)-'A';
                    adj[i][c] = true;
                    adj[c][i] = true;
                }
            }
            
            if(colorable1(adj,n)) System.out.println("1 channel needed.");
            else if(colorable2(adj,n)) System.out.println("2 channels needed.");
            else if(colorable3(adj,n)) System.out.println("3 channels needed.");
            else System.out.println("4 channels needed.");
        }
    }
    public static boolean colorable1(boolean[][] adj,int n){
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(adj[i][j]) return false;
            }
        }
        return true;
    }
    public static boolean colorable2(boolean[][] adj,int n){
        int[] col = new int[n];
        return colorable2(adj,n,col,0);
    }
    public static boolean colorable2(boolean[][] adj,int n,int[] col,int k){
        if(k==n) return true;
        
        col[k] = 0;
        boolean cont = false;
        for(int i=0;i<k;i++){
            if(adj[i][k]&&col[i]==col[k]){
                cont = true;
                break;
            }
        }
        if(!cont){
            if(colorable2(adj,n,col,k+1)) return true;
        }
        
        col[k] = 1;
        cont = false;
        for(int i=0;i<k;i++){
            if(adj[i][k]&&col[i]==col[k]){
                cont = true;
                break;
            }
        }
        if(!cont){
            if(colorable2(adj,n,col,k+1)) return true;
        }
        
        return false;
    }
    public static boolean colorable3(boolean[][] adj,int n){
        int[] col = new int[n];
        return colorable3(adj,n,col,0);
    }
    public static boolean colorable3(boolean[][] adj,int n,int[] col,int k){
        if(k==n) return true;
        
        col[k] = 0;
        boolean cont = false;
        for(int i=0;i<k;i++){
            if(adj[i][k]&&col[i]==col[k]){
                cont = true;
                break;
            }
        }
        if(!cont){
            if(colorable3(adj,n,col,k+1)) return true;
        }
        
        col[k] = 1;
        cont = false;
        for(int i=0;i<k;i++){
            if(adj[i][k]&&col[i]==col[k]){
                cont = true;
                break;
            }
        }
        if(!cont){
            if(colorable3(adj,n,col,k+1)) return true;
        }
        
        col[k] = 2;
        cont = false;
        for(int i=0;i<k;i++){
            if(adj[i][k]&&col[i]==col[k]){
                cont = true;
                break;
            }
        }
        if(!cont){
            if(colorable3(adj,n,col,k+1)) return true;
        }
        
        return false;
    }
}