AOJ :: 2107 :: Can I go there?
これ
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2107
問題概要
ある駅から駅に移動するのを1ステップとしたとき、スタート地点の駅からゴール地点の駅までちょうどZステップで行けるかどうか。
何度同じ駅を通っても良い。ただし、すぐに折り返すことはできない(A->B->Aのような移動は禁止されている)
駅(頂点)の個数は2個以上50個以下、区間(辺)の個数は1個以上50個以下、0
良問だと思う。
KステップでA地点からB地点まで行くパターン数を求めるのは、
重みなしグラフ G の隣接行列を A とすると、A^n で表される行列の (i, j) 成分は、i から j への相違なる長さ n の路の数と等しい
Wikiから引用。
行列のK乗で出来ることはわかっています。
今回はパターン数は必要ないので、隣接行列の(i,j)成分の計算は0か1の論理和で判定すれば良いことになります。
問題なのは、すぐに折り返すことができない、ということです。
どこから来たのか?と情報が必要になります。
(現在の駅、一つ前の駅)を、一つのノードとしてグラフを考えます。
駅の数が50個あるので、単純に考えると 2500個の状態ができてしまいます。
行列の掛け算の計算量は n^3 かかるので、とても間に合いません。
しかし、実際はノードの次数の合計数だけ考慮すればよく、区間数も50個以下なので状態数はM*2になります。
初期状態を考慮しても、状態数150を超えません。なんとか間に合います。
0 1 1 1 0 1 1 1 0
0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 (0,1),(0,2),(1,0),(1,2),(2,0),(2,1)というノード順
0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 (0,0),(0,1),(0,2),(1,0),(1,2),(2,0),(2,1)というノード順
あとは、行列のZ乗を計算して、スタート地点からゴール地点まで行けるパターンがあったかどうかを調べればいい。
#include <vector> #include <map> #include <algorithm> #include <iostream> using namespace std; #define REP(i,a,n) for(int i=(a); i<(int)(n); i++) #define rep(i,n) REP(i,0,n) #define all(x) (x).begin(),(x).end() #define mp make_pair #define pb push_back int n,m,z,h; int edge[64][64]; int edge2[200][200]; vector<pair<int,int> > v; vector<int> calc(const vector<int>& a, const vector<int>& b){ vector<int> ret; rep(i,h){ rep(j,h){ int sum = 0; rep(k,h){ sum |= a[i*h+k]*b[k*h+j]; } ret.pb(sum); } } return ret; } vector<int> multi(vector<int>& matrix, int k){ if( k==1 ) return matrix; vector<int> tmp = multi(matrix,k/2); if( k%2 ){ return calc(matrix,calc(tmp,tmp)); }else{ return calc(tmp,tmp); } } int main(){ while(scanf(" %d%d%d ",&n,&m,&z),n|m|z){ rep(i,64)rep(j,64)edge[i][j]=0; rep(i,200)rep(j,200)edge2[i][j]=0; v.clear(); rep(i,m){ int s,d; scanf("%d%d",&s,&d); edge[s][d] = edge[d][s] = 1; } edge[1][1] = 1; REP(i,1,n+1){ REP(j,1,n+1)if( edge[j][i]==1 ){ v.pb(mp(i-1,j-1)); } } rep(i,v.size()){ rep(j,v.size()){ if( v[i].first!=v[j].first && v[i].first==v[j].second && v[i].second!=v[j].first ){ edge2[i][j] = 1; } } } h = v.size(); vector<int> mat; rep(i,v.size()){ rep(j,v.size()){ mat.pb(edge2[i][j]); } } vector<int> hoge = multi(mat,z); bool f = false; rep(i,v.size())if( v[i].first==n-1 ){ if( hoge[i]>0 ){ f = true; break; } } puts(f?"yes":"no"); } return 0; }