[C++]최대 유량 - 백준6086

문제

• 최대 유량(백준6086)

풀이

문제 해석을 하자면,

• 문제에선 양방향에 A~Z까지 최대 유량 출력 요구
• 또한, 입력으로 A~Z, a~z 로 총 노드 52
• 또한, 파이프가 합쳐지기도 한다했으니 용량을 +로 기입
  • 참고로 용량과 유량이 같으면 포화상태이므로 접근 못함

풀이

• Ford-Fulkerson(DFS.복잡도:flow), Edmonds-Karp(BFS.복잡도:VE^2), Dinic’s Algorithm(BFS.복잡도:EV^2) 로 구현

코드

// BFS
#include<iostream>
#include<vector> // tree
#include<queue> // bfs
#include<cstring> // memset
#include<algorithm>
using namespace std;

int N; // 간선 수
int c[52][52]; // 용량 => 크기 : 대문자, 소문자 합 26+26
int f[52][52]; // 유량
vector<int> vc[52]; // tree
int visited[52];

int getID(char c) {
	if (c <= 'Z')
		return c - 'A';
	return c - 'a' + 26;
}

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

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

	// run
	int maximumFlow = 0, s = 0, t = 25; // s:A, t:Z
	while (true) {
		// init
		fill(visited, visited + 52, -1);
		queue<int> qu; // bfs
		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] || visited[nxt] != -1) continue;
				visited[nxt] = cur; // 방문기록겸 이전경로 기록
				qu.push(nxt);

				// 인접 정점이 도착지일 경우, 하나의 증가 경로를 찾았으므로, 더 이상 탐색하지 않고 종료
				if (nxt == t) break;
			}
		}
		// 더이상 증가 경로가 없는경우 종료
		if (visited[t] == -1)break;

		// 최소 유량 탐색 => 증가 경로 하나 찾으면 바로 탈출했기 때문에 거꾸로 탐색해야함
		int minF = 10000000;
		for (int i = t; i != s; i = visited[i]) {
			int nxt = visited[i];
			minF = min(minF, c[nxt][i] - f[nxt][i]);
		}

		// 유량 update
		for (int i = t; i != s; i = visited[i]) {
			int nxt = visited[i];
			f[nxt][i] += minF; // 정방향
			f[i][nxt] -= minF; // 역방향
		}

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

	cout << maximumFlow;

	return 0;
}

// DFS
#include<iostream>
#include<vector> // tree
#include<stack> // dfs
#include<cstring> // memset
#include<algorithm>
using namespace std;

int N; // 간선 수
int c[52][52]; // 용량 => 크기 : 대문자, 소문자 합 26+26
int f[52][52]; // 유량
vector<int> vc[52]; // tree
int visited[52];

int getID(char c) {
	if (c <= 'Z')
		return c - 'A';
	return c - 'a' + 26;
}

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

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

	// run
	int maximumFlow = 0, s = 0, t = 25; // s:A, t:Z
	while (true) {
		// init
		fill(visited, visited + 52, -1);
		stack<int> st; // dfs
		st.push(s);
		while (!st.empty()) {
			int cur = st.top();
			st.pop();

			for (int i = 0; i < vc[cur].size(); i++) {
				int nxt = vc[cur][i];
				if (c[cur][nxt]<=f[cur][nxt]||visited[nxt] != -1) continue;
				visited[nxt] = cur; // 방문기록겸 이존경로 기록
				st.push(nxt);

				// 인접 정점이 도착지일 경우, 하나의 증가 경로를 찾았으므로, 더 이상 탐색하지 않고 종료
				if (nxt == t) break;
			}
		}
		// 더이상 증가 경로가 없는경우 종료
		if (visited[t] == -1)break;

		// 최소 유량 탐색 => 증가 경로 하나 찾으면 바로 탈출했기 때문에 거꾸로 탐색해야함
		int minF = 10000000;
		for (int i = t; i != s; i = visited[i]) {
			int nxt = visited[i];
			minF = min(minF, c[nxt][i] - f[nxt][i]);
		}

		// 유량 update
		for (int i = t; i != s; i = visited[i]) {
			int nxt = visited[i];
			f[nxt][i] += minF; // 정방향
			f[i][nxt] -= minF; // 역방향
		}

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

	cout << maximumFlow;

	return 0;
}

/*
우선 BFS를 이용하여 잔여용량이 0 이상인 간선에 대하여 레벨 그래프(level graph)라는 것을 만들어줍니다
- 레벨 그래프 : 시작노드로부터 최단 거리로 봐도됨. BFS로 바로 구하자.
- 만약 레벨 그래프가 안만들어지는 경우엔 바로 종료.
이후 DFS 재귀형태로 나머지 연산 짜는게 편한것 같다.

참고 : https://jason9319.tistory.com/150
*/

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


int N; // 간선 수
int c[55][55]; // 용량 => 크기 : 대문자, 소문자 합 26+26
int f[55][55]; // 유량
vector<int> vc[55]; // tree
int level[55]; // 레벨 그래프
int work[55];

int getID(char c) {
	if (c <= 'Z')
		return c - 'A';
	return c - 'a' + 26;
}

bool bfs() {
	// init
	fill(level, level + 52, -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;
	char c1, c2;
	int w;
	for (int i = 0; i < N; i++) {
		cin >> c1 >> c2 >> w;
		int n1 = getID(c1); int n2 = getID(c2);
		vc[n1].push_back(n2);
		vc[n2].push_back(n1); // 양방향
		c[n1][n2] += w; // 양방향 간선이므로, 양쪽으로 용량 할당
		c[n2][n1] += w;
	}

	// run
	int maximumFlow = 0;
	while (true) {
		if (!bfs()) break; // 종료

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

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

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

느낀점

생략