【模板】 二分图匹配


网络流法题目链接:Luogu P1894 [USACO4.2]完美的牛栏The Perfect Stall
匈牙利算法题目链接:P3386 【模板】二分图匹配

匈牙利算法

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
#include <cstdio>
#include <cstring>

int n, m, e;
int res[1005];
bool chw[1005];
bool graph[1005][1005];

bool dfs(int p) {
for (int i = 1; i <= m; ++i)
if (graph[p][i] && !chw[i]) {
chw[i] = true;
if (!res[i] || dfs(res[i])) {
res[i] = p;
return true;
}
}
return false;
}

int hungary() {
int ans = 0;
for (int i = 1; i <= n; ++i) {
memset(chw, false, sizeof(chw));
if (dfs(i)) ++ans;
}
return ans;
}

int main() {
scanf("%d %d %d", &n, &m, &e);
for (int i = 1; i <= e; ++i) {
int u, v;
scanf("%d %d", &u, &v);
if (u <= n && v <= m)
graph[u][v] = true;
}
printf("%d\n", hungary());
return 0;
}

网络流法

用 Dinic 算法实现。

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
77
78
79
80
81
82
83
84
85
86
87
88
#include <cstdio>
#include <queue>
#include <algorithm>

const int inf = 0X3F3F3F3F;

struct Point {
int pta = 0, dist = 0, cur = 0;
} pt[505];
struct Path {
int cap = 0, end = 0, next = 0;
} ph[100005];

int e = 1, n, m;

void set_path(int u, int v, int w) {
ph[++e].cap = w;
ph[e].end = v;
ph[e].next = pt[u].pta;
pt[u].pta = e;
ph[++e].cap = 0;
ph[e].end = u;
ph[e].next = pt[v].pta;
pt[v].pta = e;
}

bool bfs(int s, int t) {
std::queue<int> q;
for(int i = 1; i <= 503; ++i)
pt[i].dist = inf,
pt[i].cur = pt[i].pta;
pt[s].dist = 0, q.push(s);
while(!q.empty()) {
int p = q.front();
q.pop();
for(int i = pt[p].pta; i; i = ph[i].next) {
int s = ph[i].end;
if(ph[i].cap && pt[s].dist > pt[p].dist + 1)
q.push(s), pt[s].dist = pt[p].dist + 1;
}
}
return pt[t].dist != inf;
}

int dfs(int p, int flow, int t) {
if(!flow || p == t)
return flow;
int ans = 0, temp = 0;
for(int i = pt[p].cur; i; i = ph[i].next) {
pt[p].cur = i;
int s = ph[i].end;
if(ph[i].cap && pt[s].dist == pt[p].dist + 1)
if(temp = dfs(s, std::min(flow - ans, ph[i].cap), t)) {
ans += temp,
ph[i].cap -= temp,
ph[i ^ 1].cap += temp;
if(ans >= flow) return flow;
}
}
return ans;
}

int dinic(int s, int t) {
int ans = 0, temp = 0;
while(bfs(s, t))
while(temp = dfs(s, inf, t))
ans += temp;
return ans;
}

int main() {
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; ++i)
set_path(501, i, 1);
for(int i = 1; i <= m; ++i)
set_path(i + 250, 500, 1);
for(int i = 1; i <= n; ++i) {
int cnt;
scanf("%d", &cnt);
while(cnt--) {
int v;
scanf("%d", &v);
set_path(i, v + 250, 1);
}
}
printf("%d", dinic(501, 500));
return 0;
}

 评论