백준14286 간선 끊어가기2

작성일 | In

문제 링크

  • http://icpc.me/14286

사용 알고리즘

  • Min Cut

풀이

s와 t가 비연결이 되는 시점까지 계속해서 간선을 끊어나간다고 합니다.
너무 당연하게도 min cut 문제입니다.

전체 코드

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
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int n, m;
int c[555][555];
int f[555][555];
vector<int> g[555];
int s, t;

int lv[555];
int work[555];

void addEdge(int s, int e, int x){
	g[s].push_back(e); c[s][e] += x;
	g[e].push_back(s); c[e][s] += x;
}

bool bfs(){
	memset(lv, -1, sizeof lv);
	queue<int> q; q.push(s); lv[s] = 0;
	while (q.size()){
		int now = q.front(); q.pop();
		for (auto nxt : g[now]){
			if (lv[nxt] == -1 && c[now][nxt] - f[now][nxt] > 0){
				lv[nxt] = lv[now] + 1;
				q.push(nxt);
			}
		}
	}
	return lv[t] != -1;
}

int dfs(int now, int tot){
	if (now == t) return tot;
	for (int &i = work[now]; i < g[now].size(); i++){
		int nxt = g[now][i];
		if (lv[nxt] == lv[now] + 1 && c[now][nxt] - f[now][nxt] > 0){
			int fl = dfs(nxt, min(tot, c[now][nxt] - f[now][nxt]));
			if (fl > 0){
				f[now][nxt] += fl;
				f[nxt][now] -= fl;
				return fl;
			}
		}
	}
	return 0;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < m; i++){
		int s, e, x; cin >> s >> e >> x;
		addEdge(s, e, x);
	}
	cin >> s >> t;

	int ans = 0;
	while (bfs()){
		memset(work, 0, sizeof work);
		while (1){
			int fl = dfs(s, 1e9);
			if (fl <= 0) break;
			ans += fl;
		}
	}
	cout << ans;
}