Algorithm/BOJ
축사 배정 - 2188
jhg0406
2020. 2. 11. 14:15
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
//2188 - 축사 배정
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define INF 2000000000
int N, M;
vector<vector<int>> capa, flow;
void init()
{
cin >> N >> M;
capa = flow = vector<vector<int>>(N+M+2, vector<int>(N+M+2, 0));
int n, y;
for(int i = 1; i<=N; ++i)
capa[0][i] = 1;
for(int i = 1; i<=M; ++i)
capa[i+N][N+M+1] = 1;
for(int i = 1; i<=N; ++i)
{
cin >> n;
for(int j = 0; j<n; ++j)
{
cin >> y;
y += N;
capa[i][y] = 1;
}
}
}
int networkFlow(int source, int sink)
{
int totalFlow = 0;
while(true)
{
vector<int> parent(N+M+2, -1);
queue<int> q;
parent[source] = source;
q.push(source);
while(!q.empty() && parent[sink] == -1)
{
int here = q.front(); q.pop();
for(int there = 0; there <= N+M+1; ++there)
if(capa[here][there] - flow[here][there] > 0 && parent[there] == -1)
{
q.push(there);
parent[there] = here;
}
}
if(parent[sink] == -1)
break;
int amount = INF;
for(int p = sink; p != source; p = parent[p])
amount = min(amount, capa[parent[p]][p] - flow[parent[p]][p]);
for(int p = sink; p != source; p = parent[p])
{
flow[parent[p]][p] += amount;
flow[p][parent[p]] -= amount;
}
totalFlow += amount;
}
return totalFlow;
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
init();
cout << networkFlow(0, M+N+1);
}
|
cs |
https://www.acmicpc.net/problem/2188
2188번: 축사 배정
농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 N개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다. 첫 주에는 소를 임의 배정해서 축사를 운영했으나, 곧 문제가 발생하게 되었다. 바로 소가 자신이 희망하는 몇 개의 축사 외에는 들어가기를 거부하는 것이다. 농부 존을 도와 최대한 많은 수의 소가 축사에 들어갈 수 있도록 하는 프로그램을 작성하시오. 축사의 번호는 1부터 M까지 매겨져 있다.
www.acmicpc.net
축사 배정
그래프 모델링을 위와 같이 하고, 네트워크 최대 유량 알고리즘인 Ford-Fulkerson algorithm을 사용했습니다!
