[C++/ACM] 820 Internet Bandwidth

문제: http://uva.onlinejudge.org/

external

external/8/820.html

예전에는 손도 못대던 문제가 그래프 관련 문제였다. 하지만, 의외로 많은 문제들을 그래프로 풀 수 있고 재미있는 문제들도 많다. 그래서 요새는 어떤 문제가 주어지면 혹시나

그래프로

그래프로 풀 수 있는게 아닌가부터 생각한다. 이번 문제는 문제만 읽어봐도 Maximum flow 문제라는 것을 알고리즘을 공부해본 사람은 누구나 알 수 있는 문제이다. 

학부 알고리즘 수준에서 NPC를 제외하면 제일 까다로운 부분이 아닐까 생각된다. 기초적인 부분을 제외하고 이론적으로 따지고 들면 따라가기도 꽤 어렵다. 어쨌든, 이 문제는 기본적인 Max flow 알고리즘을 따라가면서 풀면 쉽게(?) 풀린다. 가장 쉬운 Ford-Fulkerson 방식이다.

간략히 알고리즘을 살펴보자.

출발 노드(s)에서 끝 노드(t)까지 flow를 보낼 수 있는 path p를 찾아서 그 p를 이루는 edge들의 residual capacity (해당 edge로 더 보낼 수 있는 flow의 최대 크기)중에서 가장 작은 c_min를 먼저 구한다. BFS 혹은 DFS를 사용하여 해당 p가 존재하는지를 알 수 있다. p의 각 edge의 flow를 c_min만큼 증가(augment)시켜준다. 이러한 작업을 계속 하다보면 더 이상 s에서 t로 flow를 보낼 수 있는 길이 없게 되는데, 그 때 s에서 나가는 flow들의 합, 혹은 t로 들어가는 flow들의 합을 구하면 그게 Max flow가 된다.

처음에 당당히 WA(Wrong answer)를 받아서 왜 그런가 생각을 해봤다. 

1. 먼저, 마침표(.)를 안 찍은 것을 발견했다. 또 다시 WA. 
2. 이번에는 뭔가 구현상에 문제가 있는 것이 아닌가 생각을 했다. 교과서(CLRS)에는 anti-parallel edge만 존재한다고 가정한다. 따라서, 두 노드 사이에 edge가 어느 방향으로 있는지가 꽤 중요하다. augment하려는 edge가 존재하면 c_min만큼 flow를 증가시키지만, 해당 edge가 존재하지 않으면 반대 방향으로 flow를 증가, 즉, 원래 방향으로는 flow를 감소시켜야 한다. 하지만, 이 문제에서는 항상 bi-directional한 edge가 존재하므로 이 부분을 고려하지 않아도 된다고 생각했다. 그래서 다른 사람이 짠 소스를 살펴봤더니 a->b가 c_min만큼 증가되면, b->a는 c_min만큼 감소시켰다. 나도 그렇게 바꾸고 다시 제출했다. 그런데 역시 WA. 
3. 이번에는 문제를 다시 읽어봤다. 각 test case마다 newline이 있어야 한단다. 추가했더니 AC(accepted)
4. 다시 2번에서 고쳤던 부분을 원래대로 돌렸다. 역시 AC. 문제는 1, 3번이었다. 2번을 적용하도 않아도 되는 것이 맞는지, 아니면 우연히 맞은 것인지는 좀 더 생각해 봐야 한다.

#include <iostream>
#include <string.h>
#include <queue>

using namespace std;

#define INT_MAX 2147483647
#define min(a,b) ((a>=b) ? b : a)

int main() {
	int N;
	int S, T, C;	// source, destination, # of connection
	int s, d, c;
	int ac[101][101];	// array of capacity
	int af[101][101];	// array of flow
	int ap[101];	// array of parent
	bool ab[101];	// array of black & white
	queue<int> q;	// queue for BFS
	int num = 1;
	
	while (true) {
		cin >> N;
		if (N == 0) break;
			
		memset(ac, 0x00, sizeof(ac));
		memset(af, 0x00, sizeof(af));
		
		cin >> S;	// source
		cin >> T;	// destination
		
		for (cin >> C; C; C--) {	// # of connections
			cin >> s;
			cin >> d;
			cin >> c;		
			
			ac[s][d] += c;
			ac[d][s] += c;
		}

		bool isPathExist = true;

		while (isPathExist) {
			memset(ap, 0x00, sizeof(ap));
			memset(ab, 0x00, sizeof(ab));

			while (!q.empty())
				q.pop();	// make it clear
			q.push(S);
			ab[S] = true;	// set it black
			ap[S] = 0;
			
			isPathExist = false;
			while(!q.empty()) {
				int cur = q.front();
				q.pop();
	
				if (cur == T) {
					isPathExist = true;	// we found it
					break;
				}
				for (int i = 1; i <= N; i++) {
					if (ab[i] == false && (ac[cur][i] - af[cur][i]) > 0) {
						// when it is white & residual capacity > 0 
						// (there exists a connection)
						q.push(i);
						ap[i] = cur;	// cur is the parent of i
						ab[i] = true;	// set it black
					}
				}	
			}
			
			if (isPathExist == true) {
				int cur = T;
				int min = INT_MAX;
				while (cur != 0) {
					int w = (ac[ap[cur]][cur]) - (af[ap[cur]][cur]);
					if (w != 0 && min > w)
						min = w;
					cur = ap[cur];				
				}
				cur = T;
				while (cur != 0) {
					if (ap[cur] != 0)
						af[ap[cur]][cur] += min;
					cur = ap[cur];				
				}
			} else {
				int sum = 0;
				for (int i = 1; i <= N; i++)
					sum += af[S][i];
				cout << "Network " << (num++) << endl;
				cout << "The bandwidth is " << sum << "." << endl << endl;
			}
		}
	}
	
	return 0;
}