[Algorithm] cpp 백준 1210번: 마피아

[Algorithm] cpp 백준 1210번: 마피아 - 정점 분할 최소 컷

마피아의 이동을 막기 위해 톨게이트를 최소 비용으로 점거하는 문제를 정점 가중치 s-t 최소 컷으로 모델링합니다. 각 정점을 in/out으로 분할하고 내부 간선에 비용을 두어 최대 유량=최소 컷으로 풀이하며, 시작/도착 정점 점거 허용까지 반영합니다.

문제

링크: https://www.acmicpc.net/problem/1210
요약: 정점에 점거 비용이 있는 무방향 그래프에서 시작점에서 도착점까지의 모든 경로를 차단하도록 정점들을 선택하되, 총 비용의 합이 최소가 되도록 한다. 선택한 정점 번호를 오름차순으로 출력한다. (스폐셜 저지)

입력/출력

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
입력
n m
s t
c1
c2
...
cn
u1 v1
...
um vm

제한: 1 ≤ n ≤ 200, 1 ≤ m ≤ 20000, 비용 ≤ 10^7

1
2
출력
조건을 만족하는 정점(톨게이트) 번호를 오름차순으로 공백 구분 출력

접근 개요

핵심 관찰: 경로를 “정점”을 통해 차단하므로 최소 정점 컷 문제다. 정점에 비용이 있으므로 “정점 용량” 최소 컷으로 변환한다.
모델링: 각 정점 v를 v_in → v_out으로 분할하고, 내부 간선 용량을 cost[v]로 둔다. 원래 무방향 간선 (u, v)는 u_out → v_in, v_out → u_in 으로 무한대 용량을 둔다.
s/t 점거 허용: 시작/도착 정점도 점거할 수 있어야 하므로 소스는 in(s), 싱크는 out(t)로 둔다. 이렇게 하면 s나 t의 내부 간선을 끊는 선택도 가능하다.
해법: Dinic 등 최대 유량 알고리즘으로 maxflow = mincut을 구한 뒤, 잔여 그래프에서 in(v)는 도달 가능이고 out(v)는 불가인 정점 v가 최소 정점 컷에 해당한다.

알고리즘 설계

정점 분할: 모든 정점 v에 대해 in(v) → out(v) 간선을 용량 cost[v]로 추가한다.
간선 처리: 각 무방향 간선 (u, v)에 대해 out(u) → in(v)와 out(v) → in(u)에 무한대 용량을 추가한다.
소스/싱크: S = in(s), T = out(t).
최대 유량 계산: Dinic로 max_flow(S, T).
컷 복원: 소스에서 잔여 용량으로 도달 가능한 집합을 Reach라 하면, Reach(in(v)) = true이면서 Reach(out(v)) = false인 v들이 해답.

올바름 근거(스케치)

정점 용량을 내부 간선으로 치환하면, 임의의 s-t 경로는 반드시 v_in → v_out을 통과한다. 해당 간선을 자르면 그 정점은 차단된다.
무방향 간선을 양방향 무한 용량으로 두면 원래 경로 집합과 동치인 경로 집합이 보존된다.
최대 유량–최소 컷 정리에 의해 계산된 컷의 용량 합이 최소이며, 복원 규칙으로 얻은 정점 집합이 그 최소 컷을 이룬다.

복잡도

Dinic: O(E * sqrt(V))가 아닌 일반 구현 기준 O(E * V^2) 최악이지만, 실전에서는 빠르게 동작한다. 여기서는 V ≈ 2n ≤ 400, E ≈ 2m + n 범위로 충분히 통과한다.
구현 상에서는 long long으로 용량을 관리하고, 무한대는 ~1e18 근처 큰 값으로 둔다.

구현 (C++)

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
// 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
#include <bits/stdc++.h>
using namespace std;

using int64 = long long;
const int64 INF = (1LL << 60);

struct Edge {
	int to, rev;
	int64 cap;
	Edge(int t, int r, int64 c) : to(t), rev(r), cap(c) {}
};

struct Dinic {
	int N;
	vector<vector<Edge>> g;
	vector<int> level, it;
	Dinic(int n) : N(n), g(n), level(n), it(n) {}
	void add_edge(int u, int v, int64 c) {
		g[u].emplace_back(v, (int)g[v].size(), c);
		g[v].emplace_back(u, (int)g[u].size()-1, 0);
	}
	bool bfs(int s, int t) {
		fill(level.begin(), level.end(), -1);
		queue<int> q; level[s] = 0; q.push(s);
		while (!q.empty()) {
			int u = q.front(); q.pop();
			for (auto &e : g[u]) if (e.cap > 0 && level[e.to] == -1) {
				level[e.to] = level[u] + 1;
				q.push(e.to);
			}
		}
		return level[t] != -1;
	}
	int64 dfs(int u, int t, int64 f) {
		if (u == t) return f;
		for (int &i = it[u]; i < (int)g[u].size(); ++i) {
			Edge &e = g[u][i];
			if (e.cap > 0 && level[e.to] == level[u] + 1) {
				int64 ret = dfs(e.to, t, min(f, e.cap));
				if (ret > 0) {
					e.cap -= ret;
					g[e.to][e.rev].cap += ret;
					return ret;
				}
			}
		}
		return 0;
	}
	int64 max_flow(int s, int t) {
		int64 flow = 0, add;
		while (bfs(s, t)) {
			fill(it.begin(), it.end(), 0);
			while ((add = dfs(s, t, INF)) > 0) flow += add;
		}
		return flow;
	}
	vector<int> reachable_from(int s) {
		vector<int> vis(N, 0);
		stack<int> st; st.push(s); vis[s] = 1;
		while (!st.empty()) {
			int u = st.top(); st.pop();
			for (auto &e : g[u]) if (e.cap > 0 && !vis[e.to]) {
				vis[e.to] = 1; st.push(e.to);
			}
		}
		return vis;
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m;
	if (!(cin >> n >> m)) return 0;
	int s, t; cin >> s >> t; --s; --t;

	vector<int64> cost(n);
	for (int i = 0; i < n; ++i) cin >> cost[i];

	auto in = [&](int v){ return 2*v; };
	auto out = [&](int v){ return 2*v+1; };

	Dinic dinic(2*n);

	// 모든 정점에 원래 비용을 사용 (s, t 포함해서 점거 가능)
	for (int v = 0; v < n; ++v) {
		dinic.add_edge(in(v), out(v), cost[v]);
	}

	// 무방향 간선 → 양방향 무한 용량
	for (int i = 0; i < m; ++i) {
		int u, v; cin >> u >> v; --u; --v;
		dinic.add_edge(out(u), in(v), INF);
		dinic.add_edge(out(v), in(u), INF);
	}

	int S = in(s), T = out(t);
	dinic.max_flow(S, T);

	auto reach = dinic.reachable_from(S);
	vector<int> ans;
	for (int v = 0; v < n; ++v) {
		if (reach[in(v)] && !reach[out(v)]) ans.push_back(v+1);
	}
	sort(ans.begin(), ans.end());
	for (int i = 0; i < (int)ans.size(); ++i) {
		if (i) cout << ' ';
		cout << ans[i];
	}
	cout << '\n';
	return 0;
}