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;
}