元のコードでなぜ落ちるかいまだによくわかっていない。
https://community.topcoder.com/stat?c=problem_statement&pm=14596
問題
連結無向グラフがあるとする。
各頂点vに対し、頂点0からの距離D0(v)と頂点1からの距離D1(v)が与えられる。
それらの条件を満たすグラフが存在するか。存在するなら1例を示せ。
解法
なんかこれの難しい版が既出だったらしい。
http://cf16-exhibition-open.contest.atcoder.jp/tasks/codefestival_2016_ex_a
以下の2条件を満たす2頂点v-v'間に辺を張り、最後に条件に反しないかWarshall-Floyedでチェックすればよい。
- abs(D0(v)-D0(v'))≦1
- abs(D1(v)-D1(v'))≦1
class DistanceZeroAndOne { public: int N; int mat[51][51]; vector <string> construct(vector <int> D0, vector <int> D1) { vector<string> V,emp; int x,y,z; N=D0.size(); FOR(x,N) V.push_back(string(N,'N')); FOR(x,N) FOR(y,N) { if(x==y) mat[x][y]=0; else { if(abs(D0[x]-D0[y])<=1 && abs(D1[x]-D1[y])<=1) mat[x][y]=1, V[x][y]='Y'; else mat[x][y]=1010; } } FOR(z,N) FOR(x,N) FOR(y,N) mat[x][y]=min(mat[x][y],mat[x][z]+mat[z][y]); FOR(x,N) if(mat[0][x]!=D0[x] || mat[1][x]!=D1[x]) return emp; return V; } }