Bzoj 1191(二分图最大匹配)

Bzoj 1191
二分图最大匹配裸题,具体看这里

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 1000 + 5;
int cnt, n, m, lk[MAXN], vis[MAXN];
//lk[u]=i: 右边的u点被左边的i点匹配
//vis[u]=i: 第i轮左边的u点被尝试更改(不设为bool是因为这样免去每次重置数组)
vector<int> G[MAXN];
//记录左边点->右边点的边
bool hungary(int u) {
for (int i = 0; i < G[u].size(); i++) {//枚举每个右边的点匹配
int v = G[u][i];
if (vis[v] != cnt) {//尝试修改过的节点就不需要遍历了
vis[v] = cnt;
if (!lk[v] || hungary(lk[v])) {
//如果枚举的右边点没被匹配,就可以直接匹配。如果已经被匹配了,那么就让之前
//匹配这个右边点的左边点去匹配另一个点,让这个点去匹配这个右边点。
//这里运用了||的性质,||左边如果为true就不在执行||右边的表达式
lk[v] = u;
return true;//成功匹配
}
}
}
return false;
}
void clean() {
for (int i=0;i<=max(n, m);i++) vis[i] = lk[i] = 0, G[i].clear();
}
void solve() {
clean();
for (int a, b, i = 1; i <= m; i++) {//可以把u, v压行qwq
scanf("%d%d", &a, &b);
G[i].push_back(a), G[i].push_back(b);
}
int ans = 0;
for (int i = 1; i <= m; i++) {
if (hungary(cnt = i)) ans++; else break;//枚举每个左边的点匹配,如果一道题不能做出来就要break,因为不能进入下一关了,而正常二分图最大匹配这样写是不行的
}
printf("%d\n", ans);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
scanf("%d%d", &n, &m), solve();
return 0;
}

------ 本文结束 ------