Luogu P3386 【模板】二分图最大匹配

Luogu P1350 车的放置

Luogu P6062 USACO05JAN Muddy Fields G

Luogu P3355 骑士共存问题

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
bool vis[MAXnd + 10];
int match[MAXnd + 10];
bool Dfs(int cur) {
    if (vis[cur]) return 0; //
    vis[cur] = 1;			// 如果只是求最大匹配，不求最小点覆盖和最大独立集可以不用给左部点打标记，可以不加这两行。
    for (int i = head[cur]; i; i = nex[i]) {
        if (vis[to[i]]) continue;
        vis[to[i]] = 1;
        if (!match[to[i]] || Dfs(match[to[i]])) {
            match[to[i]] = cur;
            return 1;
        }
    }
    return 0;
}
int ans1, ans2, mincover[MAXnd + 10];
signed main() {
    // ......
    for (int i = 1; i <= cntleft; ++i) {
        memset(vis, 0, sizeof(vis));
        if (Dfs(i)) ++ans1;
    }
    for (int i = cntleft + 1, top = cntleft + cntright; i <= top; ++i) {
        if (match[i]) match[match[i]] = 1;
    }
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= cntleft; ++i) {
        if (!match[i]) Dfs(i);
    }
    for (int i = 1; i <= cntleft; ++i) {
        if (!vis[i]) mincover[++ans2] = i;
    }
    for (int i = cntleft + 1, top = cntleft + cntright; i <= top; ++i) {
        if (vis[i]) mincover[++ans2] = i;
    }
    // ans1 == ans2
}