[C++]간선 끊어가기 2 - 백준14286

문제

• 간선 끊어가기 2(백준14286)

풀이

문제 해석을 하자면,

• 이 문제는 Min-Cut 문제인데, 우리는 이를 Max-Flow로 풀 수 있다.

풀이

• Max-Flow 로 해결

코드

// Dinic's
#include<iostream>
#include<vector> // tree
#include<queue> // bfs
#include<algorithm> // fill
#define INF 987654321
using namespace std;

int c[505][505]; // 용량
int f[505][505]; // 유량
vector<int> vc[505]; // tree
int level[505]; // 레벨 그래프
int work[505];

int N, M, S, T; // 정점 수, 에지 수, 시작 노드, 끝 노드

bool bfs() {
	// init
	fill(level, level + 505, -1);
	queue<int> qu; // bfs
	level[S] = 0;
	qu.push(S);
	while (!qu.empty()) {
		int cur = qu.front();
		qu.pop();

		for (int i = 0; i < vc[cur].size(); i++) {
			int nxt = vc[cur][i];
			if (c[cur][nxt] <= f[cur][nxt] || level[nxt] != -1) continue;
			// 레벨이 아직 정해지지 않았고 잔여용량이 0이상은 계속 진행
			level[nxt] = level[cur] + 1; // level 기록 (그냥 깊이 기록임)
			qu.push(nxt);
		}
	}
	return level[T] != -1; // -1 이면 false 반환(종료 의미)
}

int dfs(int cur, int flow) {
	// base condition
	if (cur == T) return flow; // cur -> depth로 이해

	for (int i = work[cur]; i < vc[cur].size(); i++) {
		int nxt = vc[cur][i];
		if (level[nxt] - level[cur] != 1 || c[cur][nxt] <= f[cur][nxt]) continue;
		// 레벨 차가 1이고, 잔여용량이 0이상은 계속 진행

		// 최소 유량 탐색
		int minF = dfs(nxt, min(c[cur][nxt] - f[cur][nxt], flow));

		// 유량 update
		if (minF > 0) {
			f[cur][nxt] += minF;
			f[nxt][cur] -= minF;
			work[cur] = i; // index 기록해서 시간 단축
			return minF;
		}
	}
	work[cur] = vc[cur].size();
	return 0;
}


int main() {
	// speed up
	ios::sync_with_stdio(0);
	cin.tie(0);

	// input
	cin >> N >> M;
	int n1, n2, w;
	for (int i = 0; i < M; i++) {
		cin >> n1 >> n2 >> w;
		vc[n1].push_back(n2);
		vc[n2].push_back(n1); // 양방향
		c[n1][n2] += w; // 양방향 간선이므로, 양쪽으로 용량 할당
		c[n2][n1] += w;
	}
	cin >> S >> T;

	// run
	int maximumFlow = 0; // 제거된 최소 간선 가중치 합
	while (true) {
		if (!bfs()) break; // 종료

		fill(work, work + 505, 0);
		int flow = dfs(S, INF);

		// 최대 유량 update
		maximumFlow += flow;
	}

	// output
	cout << maximumFlow;
	return 0;
}

느낀점

생략