문제 백준 1298번노트북의 주인을 찾아서
전형적인 최대 유량 문제이다.
풀이
카테고리는 이분 매칭으로 되어있는데 애드몬드 카프로 구현해도 잘 통과 된다.
구현
|
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
|
#include<bits/stdc++.h>
using namespace std;
int c[505][505], f[505][505], pre[505];
vector<int> g[505];
vector<int> st, ta;
int main(){
int n,m; scanf(“%d %d”, &n, &m);
for(int i = 0; i < m; i++){
int u, v; scanf(“%d %d”, &u, &v);
v += n;
g[u].push_back(v);
g[v].push_back(u);
st.push_back(u);
ta.push_back(v);
c[u][v] = 1;
}
for(int x : st){
g[0].push_back(x);
g[x].push_back(0);
c[0][x] = 1;
}
for(int x : ta){
g[2*n+1].push_back(x);
g[x].push_back(2*n+1);
c[x][2*n+1] = 1;
}
int res = 0;
while(1){
memset(pre, –1, sizeof(pre));
queue<int> q;
q.push(0);
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 == 2*n+1) break;
}
}
}
if(pre[2*n+1] == –1) break;
int flow = INF;
for(int i = 2*n+1; i != 0; i = pre[i]){
flow = min(flow, c[pre[i]][i]–f[pre[i]][i]);
}
for(int i = 2*n+1; i != 0; i = pre[i]){
f[pre[i]][i] += flow;
f[i][pre[i]] –= flow;
}
res += flow;
}
printf(“%d”, res);
}
|
cs |
Leave a Reply
Your email is safe with us.