1983 Name the Crossing

「1983 Name the Crossing」の編集履歴（バックアップ）一覧はこちら

「1983 Name the Crossing」(2006/04/17 (月) 01:56:42) の最新版変更点

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

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

**1983 Name the Crossing
**問題
http://acm.pku.edu.cn/JudgeOnline/problem?id=1983
**解答方針
通りの名前を頂点とする有向グラフを考える．与えられたルールに従って「Aの水準がB以上である」といえるとき，AからBへの辺が存在するようにする．具体的には，まず入力の交差点の名前A-BごとにAからBへの辺を引く．その後，すべての頂点の組（A，B）に対して，「A，B両方との交差点が入力の中にあるような通りCがある」「D-AとB-Dが入力の中にあるような通りDはない」「A-EとE-Bが入力の中にあるような通りEはない．」のすべてが成り立つかどうかチェックし，成り立つならばAからBおよびBからAへの辺を引く．

このとき，交差点の名前X-Yがありうるのは，XからYへのパスが存在し，その長さが奇数のときである（パスの長さが偶数であることはは二つの通りが平行であることに対応している）．なお，入力の仮定によって，偶数のパスと奇数のパスが同時に存在しないことは保障されている．
**解答例
 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;
             
             String tmp[][] = new String[n][2];
             for(int i=0;i<n;i++){
                 String line = sc.next();
                 tmp[i][0] = line.substring(0,line.indexOf('-'));
                 tmp[i][1] = line.substring(line.indexOf('-')+1);
             }
             
             ArrayList<String> l = new ArrayList<String>();
             
             for(int i=0;i<n;i++){
                 if(!l.contains(tmp[i][0])) l.add(tmp[i][0]);
                 if(!l.contains(tmp[i][1])) l.add(tmp[i][1]);
             }
             
             int size = l.size();
             System.out.println(size);
             
             int matrix[][] = new int[size][size];
             
             for(int i=0;i<size;i++){
                 for(int j=0;j<size;j++){
                     matrix[i][j] = 0;
                 }
             }
             
             for(int i=0;i<n;i++){
                 int x = l.indexOf(tmp[i][0]);
                 int y = l.indexOf(tmp[i][1]);
                 matrix[x][y] = 1;
             }
             
             AMatrix a = new AMatrix(size,matrix);
             a.makepath();
             
             int m = sc.nextInt();
             
             for(int i=0;i<m;i++){
                 String line = sc.next();
                 String str1 = line.substring(0,line.indexOf('-'));
                 String str2 = line.substring(line.indexOf('-')+1);
                 int x = l.indexOf(str1);
                 int y = l.indexOf(str2);
                 int p = a.searchpath(x,y);
                 if(p%2==1) System.out.println("YES");
                 if(p%2==0) System.out.println("NO");
             }
         }
     }
 }
 
 class AMatrix{
     int size;
     int adj[][];
     
     AMatrix(int s,int m[][]){
         size = s;
         adj = m;
     }
     
     public void makepath(){
         for(int i=0;i<size;i++){
             for(int j=i+1;j<size;j++){
                 for(int k=0;k<size;k++){
                     if(k==i || k==j) continue;
                     if((adj[i][k]==1&&adj[j][k]==1)||(adj[k][i]==1&&adj[k][j]==1)){
                         int flag;
                         flag = 0;
                         for(int l=0;l<size;l++){
                             if(adj[i][l]==1&&adj[l][j]==1){
                                 flag =1;
                                 break;
                             }
                             if(adj[l][i]==1&&adj[j][l]==1){
                                 flag = 1;
                                 break;
                             }
                         }
                         if(flag==0){
                             adj[i][j] = 2;
                             adj[j][i] = 2;
                         }
                     }
                 }
             }
         }
     }
     
     public int searchpath(int x,int y){
         if(x<0 || y<0) return 0;
         
         LinkedList<Pair> l = new LinkedList<Pair>();
         HashSet<Integer> s = new HashSet<Integer>();
         l.offer(new Pair(x,0));
         s.add(x);
         while(!l.isEmpty()){
             Pair v = l.poll();
             for(int i=0;i<size;i++){
                 if(adj[v.first][i]>0){
                     if(i==y){
                         return v.second + adj[v.first][i];
                     }
                     else{
                         if(!s.contains(i)){
                             Pair u = new Pair(i,v.second+adj[v.first][i]);
                             l.offer(u);
                             s.add(i);
                         }
                     }
                 }
             }
         }
         
         return 0;
     }
 }
 
 class Pair{
     int first;
     int second;
     Pair(int a,int b){
         first = a;
         second = b;
     }
 }