SRM692 Div1 Easy "HardProof"
解法(一番早かった人のをカンニング)
通過する辺の重みにて、下回ってはいけない最小値ラインを決め打ちする。
↓
辺それぞれの重みから、決め打ちした最小値を差し引く。
↓
0 -> 1へ移動するために通る最大の重みの最小値
1 -> 0へ移動するために通る最大の重みの最小値
0 -> 2へ移動するために通る最大の重みの最小値
2 -> 0へ移動するために通る最大の重みの最小値
0 -> 3へ移動するために通る最大の重みの最小値
3 -> 0へ移動するために通る最大の重みの最小値
・・・
これらの最大値を取る(うーんとても分かりにくい説明だ・・)
↓
これらをそれぞれの最小値ラインで行い、その最小値をとれば答え
事後
全点最短経路問題であるため、ワーシャル-フロイドさんを使うと効率が良い。
しかしそれでも計算量はO(50^5) = 3億超と微妙である。
Systestは一応1秒切ったから、単純な計算を3億回とかならSRM的には問題ないっぽい。
ソースコード
int f[55][55]; int g[55][55]; class HardProof { public: int minimumCost(vector<int> D) { int n = sqrt(D.size()) + 0.5; // サイズ1なら0 if (n == 1) return 0; // f[i][j]にi->jへのコストを入れる for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { f[i][j] = D[i * n + j]; } } int INF = 200000; int ans = INF; // f[i][j]を最小値ラインとする for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i == j) continue; // 最小値ラインを加味してグラフを作成 for (int u = 0; u < n; u++) { for (int v = 0; v < n; v++) { if (f[u][v] < f[i][j]) { g[u][v] = INF; } else { g[u][v] = f[u][v] - f[i][j]; } } } // 変形ワーシャル-フロイドさん for (int w = 0; w < n; w++) { for (int u = 0; u < n; u++) { for (int v = 0; v < n; v++) { g[u][v] = min(g[u][v], max(g[u][w], g[w][v])); } } } // 0 -> 1へ移動するために通る最大の重みの最小値 // 1 -> 0へ移動するために通る最大の重みの最小値 // ・・・ // の最大値をとる int cand = 0; for (int u = 1; u < n; u++) { cand = max(cand, g[0][u]); cand = max(cand, g[u][0]); } // それぞれの最小値ラインで算出したもので最小値を取る ans = min(ans, cand); } } return ans; } };