最小カットのよい練習問題ですね。
問題概要
頂点数 、辺数
の無向単純グラフが与えられます。頂点番号を
とします。また、頂点 0 以外の
個の頂点
が与えられます。
今、次の操作を行っていくことで、頂点 0 からは頂点 のいずれにも到達できないようにしたいです (到達できないようにしたい頂点を削除することによっても達成できます)。
- 頂点
のいずれか一つを選んで削除する
- グラフの辺を 1 つ選んで削除する
操作回数の最小値を求めてください。
制約
最小カット
この問題に代えて、もし次のような問題設定でしたら、通常の最小カット問題となります。
(頂点 0 から到達させたくない頂点が 1 つだけ)
- 頂点
は削除できない
この場合は、頂点 0 と頂点 との間の辺連結度 (最小カット) を求めればよいでしょう。最小カット問題は最大流問題に帰着させて、Ford-Fulkerson 法や Dinic 法などの最大流アルゴリズムによって解くことができます。
多点を 1 点にする
さて今回は、1 頂点 と 1 頂点
の間の連結度ではなく、1 頂点
と多頂点との間の連結度を求める問題です。この場合は、新たにスーパー頂点を用意して多点と繋ぎ直す方法が有効です。
入力例 3 を例にとって考えてみましょう。下図の青頂点 (頂点 0) と赤頂点 (頂点 7, 8, 9) との間の連結度を求めたいです。
そこで、下図のようにスーパー頂点 (頂点 10) を新たに用意して、頂点 7, 8, 9 から繋ぎ直します。
こうして得られたグラフで、頂点 0 と頂点 10 との間の連結度を求めればよいでしょう。ここで、辺の容量はすべて 1 で最大フローを流せばよいです (下図)。
これによって「頂点 7, 8, 9 自体をいずれか一つ選んで削除する」というオペレーションも表現できていることに注意しましょう。つまり、上図の赤辺をカットする操作に対応します。
もし「頂点 7, 8, 9 を削除する」という操作が禁止されていたならば、下図のように赤辺に対応する要領を INF (無限大) にします。
コード
グラフを構築できたら、Ford--Fulkerson 法などの最大流アルゴリズムで解くことができます。
また、今回は無向グラフですので、辺を両方向に張ることに注意しましょう。
#include <iostream> #include <vector> 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() { // グラフの入力 // N: 頂点数、M: 辺数、K: ターゲット頂点数 int N, M, K; cin >> N >> K >> M; Graph G(N + 1); vector<int> T(K); for (int i = 0; i < K; ++i) cin >> T[i]; for (int i = 0; i < M; ++i) { int u, v; cin >> u >> v; // 容量 1 の辺 (u, v) を張る G.addedge(u, v, 1); G.addedge(v, u, 1); } // スーパー頂点に辺を張る for (auto v: T) { G.addedge(v, N, 1); G.addedge(N, v, 1); } // フォード・ファルカーソン法 FordFulkerson ff; cout << ff.solve(G, 0, N) << endl; }
