최대 유량 - 에드몬드 카프

blog.naver.com/kks227/220804885235

라이님 블로그에서 공부했음을 밝힙니다.

 

---

설명은 라이님 블로그 정독.

 

$O(min(VE^2, Ef))$

 

단방향 그래프인 경우

1. capacity를 적절한 간선에만 뚫어줘야 한다. 

2. 역방향 간선도 인접리스트에 같이 추가해줘야 한다. (capacity로 구분되는 것)

 

양방향인 경우, u-v, v-u간선에 모두 capacity를 뚫어줘야 함.

 

 

<문제>

www.acmicpc.net/problem/17412

 

각 소마다 원하는 축사가 있다. 가장 많은 소를 축사에 배정하라.

 

<풀이>

소를 향하는 더미 노드와 간선, 축사에서 향하는 더미노드와 간선을 추가해서 capacity가 1인 최대유량을 흘려주면 된다.

단방향 그래프임에 주의.

소 n마리 축사 m개인데, 축사의 정점번호는 축사번호+n으로 정함.

 

더미노드는 0과 n+m+1

 

<코드>

const int MAX = 403;
const int INF = 1e9;

int n, m, src, snk, c[MAX][MAX], f[MAX][MAX];
vector<int> g[MAX];

int main() {
	FAST; cin >> n >> m;
	src = 0, snk = n + m + 1;
	
	for (int i = 1,x,y; i <= n; i++) {
		g[0].push_back(i);
		g[i].push_back(0);
		c[0][i] = 1;
		cin >> x;
		while (x--) {
			cin >> y;
			g[i].push_back(y+n);
			g[y+n].push_back(i);
			c[i][y + n] = 1;
		}
	}

	for (int i = 1; i <= m; i++) {
		g[i + n].push_back(snk);
		g[snk].push_back(i + n);
		c[i + n][snk] = 1;
	}

	int ans = 0;
	while (1) {
		int prv[MAX];
		memset(prv, -1, sizeof(prv));
		queue<int> q;
		q.push(src);
		while (!q.empty() && prv[snk] == -1) {
			int u = q.front(); q.pop();
			if (u == snk) break;
			for (int v : g[u]) {
				if (c[u][v] - f[u][v] > 0 && prv[v] == -1) {
					prv[v] = u;
					q.push(v);
				}
			}
		}
		if (prv[snk] == -1) break;

		int flow = INF;
		for (int i = snk; i != src; i = prv[i]) 
			flow = min(flow, c[prv[i]][i]-f[prv[i]][i]);
		
		for (int i = snk; i != src; i = prv[i]) {
			f[prv[i]][i] += flow;
			f[i][prv[i]] -= flow;
		}
		
		ans += flow;
	}
	cout << ans << '\n';
}