https://community.topcoder.com/stat?c=problem_statement&pm=14596
問題概要
N頂点の連結な無向グラフがある。
これについて、頂点0から各頂点への距離dist0と頂点1から各頂点への距離dist1が分かっている。
2つの距離が満たされる無向グラフがあれば復元せよ。
解説
既出らしい。
CODE FESTIVAL 2016 Exhibition A. Distance Pairs
この問題での解法は貪欲法だが、この問題でも貪欲法を使う。
voidmaxさんの解法を参考に書いたが、こんな貪欲法で本当に通るの?って感じ。
でもプロはみんなこの解法。
コードを見てみれば早いが、「abs(d0[i] - d0[j]) <= 1 && abs(d1[i] - d1[j]) <= 1」ならば辺を頂点i,j間に辺を張るという貪欲法をやっていく。
あとは、それで正しく構築できているかをワーシャルフロイドで距離を測って、比較する。
struct DistanceZeroAndOne { vector <string> construct(vector <int> d0, vector <int> d1) { int n = d0.size(); // init vector<string> res; rep(i, 0, n) { string s = ""; rep(j, 0, n) s += "N"; res.push_back(s); } // build rep(i, 0, n) rep(j, i + 1, n) if (abs(d0[i] - d0[j]) <= 1 && abs(d1[i] - d1[j]) <= 1) res[i][j] = res[j][i] = 'Y'; // check vector<vector<int>> d(n, vector<int>(n, 10101010)); rep(i, 0, n) d[i][i] = 0; rep(i, 0, n) rep(j, 0, n) if (res[i][j] == 'Y') d[i][j] = 1; rep(k, 0, n) rep(i, 0, n) rep(j, 0, n) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); rep(i, 0, n) if (d0[i] != d[0][i]) return {}; rep(i, 0, n) if (d1[i] != d[1][i]) return {}; return res; } };