BOJ 2188 - 축사배정
아이디어
최대 유량 알고리즘을 사용한다.
가상의 source, sink과 각 소와 축사를 하나의 노드로 본다. source에서 각 소로 1이 흐를 수 있고 각 소들이 선호하는 축사로 1씩 흐를 수 있게 만든다. 그리고 모든 축사에서 sink로 1씩 흐를 수 있게 만든다. 모든 소는 자기가 원하는 축사로만 흐를 수 있고 sink로 흐를 수 있는 노드는 축사밖에 없으므로 source -> sink로 흐를 수 있는 최대 유량을 구하면 답을 구할 수 있다.
소스
#include <algorithm> //sort
#include <climits>
#include <cstring> //memset
#include <functional> //greater
#include <iostream>
#include <queue>
#include <utility> //pair
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define reap(i, a, b) for (int i = a; i < b; i++)
#define in1(a) cin >> a;
#define in2(a, b) cin >> a >> b;
#define in3(a, b, c) cin >> a >> b >> c;
#define in4(a, b, c, d) cin >> a >> b >> c >> d;
#define out1(a) cout << a << endl;
#define out2(a, b) cout << a << " " << b << endl;
#define out3(a, b, c) cout << a << " " << b << " " << c << endl;
#define out4(a, b, c, d) cout << a << " " << b << " " << c << " " << d << endl;
// 1. 소, 축사 하나 당 노드 한개 + 입력, 출구 노드 => 총 N+M+2개. N, M <= 200
// 2. 입력노드는 각 소 노드로 1마리씩 흐른다.
// 3. 소 노드는 그 소가 선호하는 축사 노드로 1의 파이프를 갖는다.
// 4. 모든 축사는 출구 노드로 1의 용량을 가진다.
// 이제 최대 유량 구해서 흐르는 소를 구하면 답.
// 0: source, 1: sink, 100~299: cow, 300~499: 축사
#define MAX_MAP_SIZE 100 + 200 + 200
int flow[MAX_MAP_SIZE][MAX_MAP_SIZE], capacity[MAX_MAP_SIZE][MAX_MAP_SIZE];
int N, M;
int cow_offset = 2, house_offset;
int map_size;
int solve();
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
memset(flow, 0, sizeof(flow));
memset(capacity, 0, sizeof(capacity));
in2(N, M);
house_offset = 2 + N;
map_size = 2 + N + M;
reap(i, 0, N) {
// source to cow
capacity[0][cow_offset + i] = 1;
// cow to house
int S, temp;
in1(S);
reap(j, 0, S) {
in1(temp);
capacity[cow_offset + i][house_offset + temp - 1] = 1;
}
}
// house to sink
reap(i, 0, M) { capacity[house_offset + i][1] = 1; }
int answer = solve();
out1(answer);
return 0;
}
// 0 -> 1 길 찾기
bool bfs(int *parent) {
queue<int> q;
q.push(0);
while (!q.empty()) {
int cur = q.front();
q.pop();
reap(i, 0, map_size + 1) {
if (parent[i] == -1 && capacity[cur][i] > flow[cur][i]) {
parent[i] = cur;
if (i == 1)
return true;
q.push(i);
}
}
}
return false;
}
// 0 -> 1 최대 유량 구하기
int solve() {
int res = 0;
int parent[MAX_MAP_SIZE];
while (true) {
memset(parent, -1, sizeof(parent));
if (!bfs(parent))
break;
// 유량 구하기
int max_flow = INT_MAX;
// out1("");
for (int cur = 1; cur != 0; cur = parent[cur]) {
// out1(cur);
int p = parent[cur];
max_flow = min(max_flow, capacity[p][cur] - flow[p][cur]);
}
// update
for (int cur = 1; cur != 0; cur = parent[cur]) {
int p = parent[cur];
flow[p][cur] += max_flow;
flow[cur][p] -= max_flow;
}
res += max_flow;
}
return res;
}