今天我刷题了吗
搜索文档…
Hungary 算法
1
#include <bits/stdc++.h>
2
3
using namespace std;
4
using ll = long long;
5
using p = pair<int, int>;
6
const double pi(acos(-1));
7
const int inf(0x3f3f3f3f);
8
const int mod(1e9 + 7);
9
const int maxn(1e3 + 10);
10
const int maxm(1e5 + 10);
11
int ecnt, head[maxn];
12
bool vis[maxn];
13
int match[maxn];
14
15
struct edge {
16
int to, nxt;
17
} edges[maxm];
18
19
template<typename T = int>
20
inline const T read()
21
{
22
T x = 0, f = 1;
23
char ch = getchar();
24
while (ch < '0' || ch > '9') {
25
if (ch == '-') f = -1;
26
ch = getchar();
27
}
28
while (ch >= '0' && ch <= '9') {
29
x = (x << 3) + (x << 1) + ch - '0';
30
ch = getchar();
31
}
32
return x * f;
33
}
34
35
template<typename T>
36
inline void write(T x, bool ln)
37
{
38
if (x < 0) {
39
putchar('-');
40
x = -x;
41
}
42
if (x > 9) write(x / 10, false);
43
putchar(x % 10 + '0');
44
if (ln) putchar(10);
45
}
46
47
void addEdge(int u, int v)
48
{
49
edges[ecnt].to = v;
50
edges[ecnt].nxt = head[u];
51
head[u] = ecnt++;
52
}
53
54
bool dfs(int u)
55
{
56
for (int i = head[u]; compl i; i = edges[i].nxt) {
57
int v = edges[i].to;
58
if (not vis[v]) {
59
vis[v] = true;
60
if (not match[v] or dfs(match[v])) {
61
match[v] = u;
62
return true;
63
}
64
}
65
}
66
return false;
67
}
68
69
int hungary(int n)
70
{
71
int res = 0;
72
for (int i = 1; i <= n; ++i) {
73
memset(vis, false, sizeof vis);
74
res += dfs(i);
75
}
76
return res;
77
}
78
79
int main()
80
{
81
#ifdef ONLINE_JUDGE
82
#else
83
freopen("input.txt", "r", stdin);
84
#endif
85
ios::sync_with_stdio(false);
86
memset(head, -1, sizeof head);
87
int n = read(), m = read(), e = read();
88
while (e--) {
89
int u = read(), v = read() + n;
90
addEdge(u, v);
91
addEdge(v, u);
92
}
93
write(hungary(n), true);
94
return 0;
95
}
Copied!
最近更新 1yr ago
复制链接