AOJ2107 Can I go there?

AOJ Volume21

問題リンク Can I go there?

  • 解法

長らく悩んでいた問題なんですが、折れて答えを調べました。
次のすげぇ性質を使うようです

行列A^kの(i, j)成分を、頂点iから頂点jへkステップで到達できるなら1、そうでないなら0、と決めると
A^1 = グラフの隣接行列
A^m * A^n = A^(m+n)
つまり、駅をグラフにして、その隣接行列のZ乗を繰り返し2乗法で求めればZステップの経路が存在するかどうか判定できる、と。
ただ、この問題では、駅はただちに引き返してはならないといううざったい制約があるので少しグラフを変形する必要があります。頂点を(1ステップ前の駅、現在の駅）としてやります。普通に考えると頂点数がN^2になって隣接行列の要素数がとんでもないことになりますが、実際に存在する頂点は辺の本数の2倍だけです。頂点sとtを結ぶ線路があったら、(s, t)と(t, s)という頂点が生まれます。これらの頂点における隣接行列を作ります。(a, b)と(c, d)という頂点が隣接しているための条件は
b == c かつ a != d
です。
更に、スタートを表す頂点Sを1個追加します。Sと(1, *)となっている頂点kをA[S][k] = 1という風に結びます。後は、この隣接行列のZ乗を求めて、
k == N && A[S][k] != 0
という成分が見つかるかどうかで判定します。
尚、A^kの(i, j)成分は、頂点iからjへkステップで到達する経路の本数と等しいのでそのうちオーバーフローを起こします。成分を常に{0, 1}にするといいでしょう。

  • ソース
import java.util.Scanner;

//Can I go there?
public class AOJ2107 {

	long[][] modpow(long[][] A, long n){
		long[][] res = new long[A.length][A.length];
		for(int i=0;i<A.length;i++){
			res[i][i] = 1L;
		}
		while(n>0){
			if((n&1)>0){
				res = modmul(res, A);
				for(int i=0;i<A.length;i++)for(int j=0;j<A.length;j++)res[i][j] = Math.min(res[i][j], 1);
			}
			A = modmul(A, A);
			for(int i=0;i<A.length;i++)for(int j=0;j<A.length;j++)A[i][j] = Math.min(A[i][j], 1);
			n>>=1;
		}
		return res;
	}
	
	long[][] modmul(long[][] A, long[][] B){
		long[][] res = new long[A.length][B[0].length];
		for(int i=0;i<A.length;i++){
			for(int j=0;j<B[0].length;j++){
				for(int k=0;k<A[0].length;k++){
					res[i][j] = (res[i][j] + A[i][k]*B[k][j]);
				}
			}
		}
		return res;
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			int n = sc.nextInt(), m = sc.nextInt(), Z = sc.nextInt();
			if((n|m|Z)==0)break;
			int[] pre = new int[2*m], now = new int[2*m];
			for(int i=0;i<m;i++){
				int s = sc.nextInt(), t = sc.nextInt();
				pre[i*2] = s; now[i*2] = t;
				pre[i*2+1] = t; now[i*2+1] = s;
			}
			long[][] A = new long[2*m+1][2*m+1];
			for(int i=0;i<2*m;i++)for(int j=0;j<2*m;j++){
				if(now[i]==pre[j] && now[j]!=pre[i])A[i][j] = 1;
			}
			for(int i=0;i<2*m;i++)if(pre[i]==1)A[2*m][i] = 1;
			A = modpow(A, Z);
			String res = "no";
			for(int i=0;i<2*m;i++){
				if(now[i]==n && A[2*m][i]!=0){
					res = "yes"; break;
				}
			}
			System.out.println(res);
		}
	}
	
	public static void main(String[] args) {
		new AOJ2107().run();
	}
}