TopCoder SRM 584 Div1 Easy Egalitarianism
問題
n人の人がいて、isFriend[i][j]が'Y'であるときi, jは友達同士である。
(i, jが友達のときj, iも友達である)
友達同士の所持金の差はd以下である。
このとき、n人の中で、所持金の最大値と最小値の差は、最大でいくらになるか。
最大値が存在しないときは-1を返せ。
制約条件
n≦50
d≦1000
方針
最小値になる人を決めて牛ゲーした。(寝ぼけていた)
本当は、最小値になる人を決めたら牛ゲーしなくても、最短距離が一番遠い人の距離 * dが最大値になる。
これを全ての最小値になる人について試せばよい。
ソースコード
class Egalitarianism { public: int maxDifference(vector <string> isFriend, int d) { int n = isFriend.size(); int e[50][50], dist[50]; rep(i, n) rep(j, n) e[i][j] = i == j ? 0 : inf; rep(i, n) rep(j, n){ if(isFriend[i][j] == 'N') continue; e[j][i] = min(e[j][i], d); e[i][j] = min(e[i][j], d); } ll ans = 0; rep(zero, n){ rep(i, n) dist[i] = i == zero ? 0 : inf; rep(it, n){ bool update = 0; rep(i, n) rep(j, n) if(dist[i] > dist[j] + e[j][i]){ update = 1; dist[i] = dist[j] + e[j][i]; if(it == n - 1) return -2; } if(!update) break; } ll res = *max_element(dist, dist + n) - *min_element(dist, dist+ n); ans = max(ans, res); } if(ans == inf) return -1; return ans; } };