Indeedなう（本選A） : E - Page Rank

これでいいの…？
http://indeednow-finala-open.contest.atcoder.jp/tasks/indeednow_2015_finala_e

問題

N人の社員がおり、それぞれが優秀だと思う社員のリストを持つ。
社員と優秀だと思う社員の関係を有向辺で表したグラフを考える。

i番目の社員のページランクをPR(i)としたとき、

が成り立つとする。(M(i)はjを尊敬している社員の集合、N(j)がjが尊敬している社員の集合)

PR(i)を求めよ。

解法

1つは連立方程式を愚直に解けばよい。

もう一つ解法がある。
この式はPage Rankの伝搬の式そのものである。
よって初期状態をPR(i)とし、上記式を1000回位ループすると誤差の範囲内まで収束する。

int N,M;
int SP[10100];
vector<int> E[10100];
double P[2][10100];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) cin>>x>>y, E[y-1].push_back(x-1), SP[x-1]++;
	FOR(i,N) P[0][i]=1;
	FOR(i,1000) {
		int cur=i%2,tar=cur^1;
		FOR(j,N) {
			P[tar][j]=0;
			FORR(r,E[j]) P[tar][j] += P[cur][r]/SP[r];
			P[tar][j]=P[tar][j]*0.9+0.1;
		}
	}
	FOR(i,N) _P("%.12lf\n",P[0][i]);
}

まとめ

考えたらどこにもPR(i)=1が初期値なんて書いてないのか。
何も考えずPage Rankの計算ぶん回したらあっさり通ってしまったのでびっくり。