二分匹配

数据结构与算法
字数统计: 245字   |   阅读时长≈ 1分钟

二分匹配的总结

HYSBZ - 1143 祭祀river (二分图最大匹配)

1
#include <bits/stdc++.h>
2
using namespace std;
3
int a[105][105] = {0};
4
int pre[205], s[205] = {0}, vis[105];
5
int cat(int x, int n)
6
{
7
    int i;
8
    for(i = 1; i <= n; i++)
9
    {
10
        if(vis[i] == 0 && a[x][i])
11
        {
12
            vis[i] = 1;
13
            if(!s[i] || cat(s[i], n))
14
            {
15
                s[i] = x;
16
                return 1;
17
            }
18
        }
19
    }
20
    return 0;
21
}
22
int main()
23
{
24
    int n, m, i, j, k, u, v;
25
    scanf("%d %d", &n, &m);
26
    for(i = 1; i <= m; i++)
27
    {
28
        scanf("%d %d", &u, &v);
29
        a[u][v] = 1;
30
    }
31
    for(k = 1; k <= n; k++)
32
    {
33
        for(i = 1; i <= n; i++)
34
        {
35
            for(j = 1; j <= n; j++)
36
            {
37
                if(a[i][k] == 1 && a[k][j] == 1)a[i][j] = 1;
38
            }
39
        }
40
    }
41
    int ans = 0;
42
    for(i = 1; i <= n; i++)
43
    {
44
        memset(vis, 0, sizeof(vis));
45
        if(cat(i, n))ans++;
46
    }
47
    printf("%d\n", n - ans);
48
}
  • © 2020 QSH
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信