「最短路に含まれる可能性のある辺を列挙する」という考え方と、最小カットを組み合わせます。教育的な良問といえますね。
なお、この問題の設定を少し変えると非常に難しい問題が得られることも知られています (難しい問題: AOJ 2230 How to Create a Good Game)。
問題概要
頂点
辺の重み付き有向グラフが与えられます。
グラフの各辺の重みを適切に増やすことで、2 頂点 間の最短路長を増やしたいとします。各辺
の重みを 1 増やすのに必要なコストが
で与えられます。
-
間の最短路長を 1 以上増やすのに必要な最小コストを求めてください。
制約
考えたこと
教育的な良問ですね。まず、頂点 間の最短経路として考えられるものはいろいろ考えられますが、そのいずれの経路にも含まれないような辺については、伸ばしても特に意味がないといえます。よって、最短経路に含まれる可能性のある辺のみで構成されるグラフを考えてみましょう。
なおそのための方法は、下の問題とほぼ同様です。下の問題と同様の解放によって、最短経路に含まれる可能性のある辺を抽出することができます。具体的には
- Floyd--Warshall 法などによって、全頂点間の最短路 (2 頂点
間の距離を
dist[u][v]とする) を求めておく - 辺
が「いずれかの最短経路に含まれるか」を判定するためには、
dist[s][u]+c(e)+dist[v][t]==dist[s][t]かどうかを調べればよい
という方法でできます。この部分の計算量は となります。
実はこのグラフ (各辺 の容量を
とする) の最小カットが求める最小コストになるのです。
まず、仮にコストを増大させる辺の集合が「カット」になっていないとすると、どの辺もコストがそのままの -
パスが残存することを意味してしまいます。逆に、コストを増大させる辺の集合が「カット」になっていれば、コストがそのままの辺のみを使って
から
へと到達することはできません。
以上から、最小カット問題へと帰着されましたので、Ford--Fulkerson 法などのアルゴリズムによって解くことができます。
コード
#include <bits/stdc++.h> using namespace std; // グラフを表す構造体 struct Graph { // 辺を表す構造体 // rev: 逆辺 (to, from) が G[to] の中で何番目の要素か // cap: 辺 (from, to) の容量 struct Edge { int rev, from, to, cap; Edge(int r, int f, int t, int c) : rev(r), from(f), to(t), cap(c) {} }; // 隣接リスト vector<vector<Edge>> list; // N: 頂点数 Graph(int N = 0) : list(N) { } // グラフの頂点数取得 size_t size() { return list.size(); } // Graph インスタンスを G として， // G.list[v] を G[v] と書けるようにしておく vector<Edge> &operator [] (int i) { return list[i]; } // 辺 e = (u, v) の逆辺 (v, u) を取得する Edge& redge(const Edge &e) { return list[e.to][e.rev]; } // 辺 e = (u, v) に流量 f のフローを流す // e = (u, v) の流量が f だけ減少する // このとき逆辺 (v, u) の流量を増やす void run_flow(Edge &e, int f) { e.cap -= f; redge(e).cap += f; } // 頂点 from から頂点 to へ容量 cap の辺を張る // このとき to から from へも容量 0 の辺を張っておく void addedge(int from, int to, int cap) { int fromrev = (int)list[from].size(); int torev = (int)list[to].size(); list[from].push_back(Edge(torev, from, to, cap)); list[to].push_back(Edge(fromrev, to, from, 0)); } }; struct FordFulkerson { static const int INF = 1 << 30; // 無限大を表す値を適切に vector<int> seen; FordFulkerson() { } // 残余グラフ上で s-t パスを見つける (深さ優先探索) // 返り値は s-t パス上の容量の最小値 (見つからなかったら 0) // f: s から v へ到達した過程の各辺の容量の最小値 int fodfs(Graph &G, int v, int t, int f) { // 終端 t に到達したらリターン if (v == t) return f; // 深さ優先探索 seen[v] = true; for (auto &e : G[v]) { if (seen[e.to]) continue; // 容量 0 の辺は実際には存在しない if (e.cap == 0) continue; // s-t パスを探す // 見つかったら flow はパス上の最小容量 // 見つからなかったら f = 0 int flow = fodfs(G, e.to, t, min(f, e.cap)); // s-t パスが見つからなかったら次辺を試す if (flow == 0) continue; // 辺 e に容量 flow のフローを流す G.run_flow(e, flow); // s-t パスを見つけたらパス上最小容量を返す return flow; } // s-t パスが見つからなかったことを示す return 0; } // グラフ G の s-t 間の最大流量を求める // ただしリターン時に G は残余グラフになる int solve(Graph &G, int s, int t) { int res = 0; // 残余グラフに s-t パスがなくなるまで反復 while (true) { seen.assign((int)G.size(), 0); int flow = fodfs(G, s, t, INF); // s-t パスが見つからなかったら終了 if (flow == 0) return res; // 答えを加算 res += flow; } // no reach return 0; } }; int main() { // 入力 int N, M, s, t; cin >> N >> M >> s >> t; --s, --t; // 距離行列とコスト行列 const long long INF = 1LL<<60; vector<vector<long long>> dist(N, vector<long long>(N, INF)); vector<vector<long long>> cap(N, vector<long long>(N, INF)); for (int i = 0; i < M; ++i) { int u, v, d, c; cin >> u >> v >> d >> c; --u, --v; dist[u][v] = d; cap[u][v] = c; } // Floyd--Warshall vector<vector<long long>> dp(N, vector<long long>(N, INF)); for (int u = 0; u < N; ++u) { for (int v = 0; v < N; ++v) dp[u][v] = dist[u][v]; dp[u][u] = 0; } for (int k = 0; k < N; ++k) for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]); // フローを流すためのグラフを作る Graph G(N); for (int u = 0; u < N; ++u) { for (int v = 0; v < N; ++v) { if (u == v) continue; // 判定 if (dp[s][u] + dist[u][v] + dp[v][t] == dp[s][t]) { G.addedge(u, v, cap[u][v]); } } } // 最小カットを求める FordFulkerson ff; cout << ff.solve(G, s, t) << endl; }
