문제 : 백준 11378번 열혈 강호4
네트워크 플로우 문제이다. 배정해주는 일의 개수의 최대는 그래프에서 흐르는 최대 유량이 된다.
https://www.acmicpc.net/problem/11378
풀이
모든 사람이 최대 1개의 일을 할 수 있기 때문에 소스에서 사람으로 가는 유량이 최대 1개인 간선으로 이어준다. 그런데 벌점을 받을 때마다 추가로 일을 더 할 수 있다. 여기서 주의할 점은 벌점을 다 써버리면 나머지 사람은 최대 1개의 일밖에 하지 못한다는 것이다. 따라서 포트 노드를 따로 하나 만들어 최대 k만큼의 유량이 들어가고 k만큼이 사람들에게로 나가게끔 연결해주면 된다. 배정하고자하는 일의 최대 개수는 그래프에서 흐르는 유량의 최댓값과 같다.
에드몬드 카프 알고리즘으로 구현해주면 시간 복잡도 O(mn2) 만에 수행 가능하다.
자주 실수하는 틀린 구현의 예시를 하나 소개해보겠다. 벌점이 10점이라고 해보자. 10의 벌점을 한명이 다 소진해버린 경우 나머지 사람은 최대 1의 일밖에 하지 못한다. 그러나 아래와 같은 그래프에서는 다 소진해버려도 최대 3의 flow가 흐를 수 있다. 따라서 포트 노드를 반드시 따로 만들어서 구현해주어야 한다.
코드
구현은 애드몬드 카프 알고리즘으로 쉽게 할 수 있다. 시간 복잡도가 109 시간이기는 한데 제한시간이 3초라 그런지 통과가 잘된다.
|
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
76
|
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll c[2020][2020], f[2020][2020];
int pre[2020];
vector<ll> g[2020];
int main(){
int n,m; ll k; scanf(“%d %d %lld”, &n, &m, &k);
for(int i = 1; i <= n; i++){
int nu; scanf(“%d”, &nu);
while(nu––){
int u; scanf(“%d”, &u);
u += n;
g[i].push_back(u);
g[u].push_back(i);
c[i][u] = 1;
}
}
const int s = n+m+1;
const int e = n+m+2;
for(int i = 1; i <= n; i++){
g[s].push_back(i);
g[i].push_back(s);
c[s][i] = 1;
}
g[s].push_back(0);
g[0].push_back(s);
c[s][0] = k;
for(int i = 1; i <= n; i++){
g[0].push_back(i);
g[i].push_back(0);
c[0][i] = k;
}
for(int i = n+1; i <= n+m; i++){
g[i].push_back(e);
g[e].push_back(i);
c[i][e] = 1;
}
ll res = 0;
while(1){
memset(pre, –1, sizeof(pre));
queue<int> q;
q.push(s);
while(!q.empty()){
int now = q.front();
q.pop();
for(int nxt : g[now]){
if(c[now][nxt]–f[now][nxt] > 0 && pre[nxt]== –1){
q.push(nxt);
pre[nxt] = now;
if(nxt == e) break;
}
}
}
if(pre[e] == –1) break;
ll flow = LINF;
for(int i = e; i != s; i = pre[i]){
flow = min(flow, c[pre[i]][i]–f[pre[i]][i]);
}
for(int i = e; i != s; i = pre[i]){
f[pre[i]][i] += flow;
f[i][pre[i]] –= flow;
}
res += flow;
}
printf(“%lld”, res);
}
|
cs |
Leave a Reply
Your email is safe with us.