1417 True Liars

「1417 True Liars」の編集履歴（バックアップ）一覧はこちら

「1417 True Liars」(2006/04/16 (日) 23:21:02) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

**1417 True Liars
**問題
http://acm.pku.edu.cn/JudgeOnline/problem?id=1417
**解答方針
"i j yes" からは i と j が同じ種族であることがわかります．"i j no" からは i と j が違う種族であることがわかります．逆に，それ以上の情報は得られません．
これを利用して，島の住人を「そのグループのうち一人の種族が決まれば他の全員の種族も決まるようなグループ」に分割します．プログラム中ではStep1，Step2に該当します．こうすることで，探索空間の大きさを「2^(住人の数)」から「2^(グループの数)」に減らすことができます．グループの代表者の種族さえ決めればよいからです．ただ，これでもまだ探索空間は十分大きいので，枝刈りを適切に行う必要があります．
**解答例
 import java.util.*;
 
 public class Main {
     public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
         while(true){
             int n = sc.nextInt();
             int p1 = sc.nextInt();
             int p2 = sc.nextInt();
             if(n==0&&p1==0&&p2==0) break;
             ArrayList<Question> ques = new ArrayList<Question>();
             for(int i=0;i<n;i++){
                 int x = sc.nextInt()-1;
                 int y = sc.nextInt()-1;
                 boolean a = sc.next().equals("yes");
                 ques.add(new Question(x,y,a));
             }
             
             Solver sol = new Solver(p1,p2,ques);
             sol.solve();
         }
     }
 }
 
 class Solver{
     int p;
     int p1;
     int p2;
     Question[] ques;
     
     int[] group;
     boolean[] relative;
     
     int groupnum;
     boolean[] assign;
     int[] assign_yes;
     int[] assign_no;
     HashMap<SearchState,Boolean> searched;
     
     boolean ans_exist;
     boolean[] ansassign;
     
     Solver(int p1, int p2,ArrayList<Question> ques) {
         this.p1 = p1;
         this.p2 = p2;
         this.p = p1 + p2;
         this.ques = new Question[ques.size()];
         this.ques = ques.toArray(this.ques);
         group = new int[p];
         relative = new boolean[p];
         for(int i=0;i<p;i++){
             group[i] = i;
             relative[i] = true;
         }
     }
     
     public void solve(){
         //Step1 merge the groups
         merge_groups();
         
         //Step2 rename the group id
         groupnum = rename_groups();
         
         //Step3 search
         search_init();
         search();
         
         //Step4 print
         print();
     }
 
     private void print(){
         if(!ans_exist) System.out.println("no");
         else{
             boolean ans[] = new boolean[p];
             for(int i=0;i<p;i++){
                 ans[i] = relative[i] ^ !ansassign[group[i]];
             }
             for(int i=0;i<p;i++){
                 if(ans[i]) System.out.println(i+1);
             }
             System.out.println("end");
         }
     }
     
     private void search_init(){
         assign_yes  = new int[groupnum];
         assign_no = new int[groupnum];
         
         for(int i=0;i<groupnum;i++){
             assign_yes[i] = 0;
             assign_no[i] = 0;
         }
         for(int i=0;i<p;i++){
             if(relative[i]) assign_yes[group[i]]++;
             else assign_no[group[i]]++;
         }
         
         assign = new boolean[groupnum];
         searched = new HashMap<SearchState,Boolean>();
     }
     
     private void search(){
         ans_exist = false;
         ansassign = null;
         
         try{
             search_sub(0,0,0);
         }
         catch(AnswerNotExistsException e){
             //do nothing
         }
     }
     
     private void search_sub(int lp1,int lp2,int k) throws AnswerNotExistsException{
         // leaf of DFS
         if(k==groupnum){
             if(lp1==p1&&lp2==p2){
                 if(ans_exist){
                     ans_exist = false;
                     ansassign = null;
                     throw new AnswerNotExistsException();
                 }
                 else{
                     ans_exist = true;
                     ansassign = new boolean[groupnum];
                     for(int i=0;i<groupnum;i++) ansassign[i] = assign[i];
                 }
             }
         }
         // node of DFS
         else{
             SearchState tmp = new SearchState(lp1,lp2,k);
             
             //when this state has searched yet
             if(searched.containsKey(tmp)){
                 if(searched.get(tmp)){
                     ans_exist = false;
                     ansassign = null;
                     throw new AnswerNotExistsException();
                 }
                 else{
                     return;
                 }
             }
             //when this state has not searchet yet
             else{
                 searched.put(tmp,false);
                 
                 boolean ori_ans_exist = ans_exist;
                 
                 //search next state
                 assign[k] = true;
                 if(lp1<=p1&&lp2<=p2) search_sub(lp1+assign_yes[k],lp2+assign_no[k],k+1);
                 assign[k] = false;
                 if(lp1<=p1&&lp2<=p2) search_sub(lp1+assign_no[k],lp2+assign_yes[k],k+1);
                 
                 // find solution from this state
                 if(!ori_ans_exist&&ans_exist){
                     searched.put(tmp,true);
                 }
             }
         }
     }
     
     private void merge_groups() {
         for(int i=0;i<ques.length;i++){
             int x = ques[i].x;
             int y = ques[i].y;
             boolean ans = ques[i].ans;
             if(group[x]!=group[y]){
                 if(ans) merge_yes(x,y);
                 else merge_no(x,y);
             }
         }
     }
     
     private void merge_yes(int x,int y){
         int gx = group[x];
         int gy = group[y];
         if(relative[x]!=relative[y]){
             for(int i=0;i<p;i++){
                 if(group[i]==gy) relative[i] = !relative[i];
             }
         }
         
         for(int i=0;i<p;i++){
             if(group[i]==gy) group[i] = gx;
         }
     }
     private void merge_no(int x,int y){
         int gx = group[x];
         int gy = group[y];
         if(relative[x]==relative[y]){
             for(int i=0;i<p;i++){
                 if(group[i]==gy) relative[i] = !relative[i];
             }
         }
         
         for(int i=0;i<p;i++){
             if(group[i]==gy) group[i] = gx;
         }
     }
     private int rename_groups(){
         int groupnum = 0;
         for(int i=0;i<p;i++){
             if(i==group[i]) groupnum++;
         }
         
         HashMap<Integer,Integer> m = new HashMap<Integer,Integer>();
         int gidcnt = 0;
         for(int i=0;i<p;i++){
             if(i==group[i]){
                 m.put(i,gidcnt);
                 gidcnt++;
             }
         }
         
         for(int i=0;i<p;i++){
             group[i] = m.get(group[i]);
         }
         
         return groupnum;
     }
 }
 
 class SearchState{
     int p1;
     int p2;
     int k;
     SearchState(int p1, int p2, int k) {
         this.p1 = p1;
         this.p2 = p2;
         this.k = k;
     }
     public boolean equals(Object o){
         SearchState s = (SearchState)o;
         return this.p1==s.p1&&this.p2==s.p2&&this.k==s.k;
     }
     public int hashCode(){
         return p1<<24+p2<<8+k;
     }
 }
 
 class Question{
     int x;
     int y;
     boolean ans;
     Question(int x, int y, boolean ans) {
         this.x = x;
         this.y = y;
         this.ans = ans;
     }
 }
 
 class AnswerNotExistsException extends Exception{
    
 }