首页 > 代码库 > 二分图匹配 最大匹配数+最大点覆盖 POJ 1469+POJ 3041

二分图匹配 最大匹配数+最大点覆盖 POJ 1469+POJ 3041

2024-07-07 03:20:14   230人阅读

最大匹配数就等于最大点覆盖，因为在图里面，凡是要覆盖的点必定是连通的，而最大匹配之后，若还有点没有覆盖到，则必定有新的匹配，与最大匹配数矛盾，如果去掉一些匹配，则必定有点没有覆盖到。

POJ 1469

比较简单，用的经典的二分图匹配算法。

?
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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int p[500][510],c[500][510];
int vis[510];
int lefts[510];
int cp[500],cc[500],n,m;
void init()
{
    memset(vis,0,sizeof vis);
    memset(lefts,-1,sizeof lefts);
    memset(cp,0,sizeof cp);
    memset(cc,0,sizeof cc);
    memset(p,0,sizeof p);
    memset(c,0,sizeof c);
}
bool match(int u)
{
    for (int j=0;j<cp[u];j++){
        int v=p[u][j];
        if (1){
            vis[v]=1;
            if (lefts[v]==-1 || match(lefts[v])){
                lefts[v]=u;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        init();
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;i++){
            int tmp,t2;
            scanf("%d",&tmp);
            for (int j=0;j<tmp;j++){
                scanf("%d",&t2);
                p[t2][cp[t2]++]=i;
                c[i][cc[i]++]=t2;
            }
        }
        int ans=0;
        for (int i=1;i<=m;i++){
            memset(vis,0,sizeof vis);
            if (match(i)) ans++;
        }
        //cout<<ans<<endl;
        if (ans==n) puts("YES");
        else  puts("NO");
 
    }
    return 0;
}

　　

 

POJ 3041

最小覆盖问题，转化为求最大匹配

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int mat[510][510],cnt[510];
int vis[510],lefts[510];
int n,k;
bool match(int u)
{
    for (int i=0;i<cnt[u];i++){
        int v=mat[u][i];
        if (!vis[v]){
            vis[v]=1;
            if (lefts[v]==-1 || match(lefts[v])){
                lefts[v]=u;
                return true;
            }
        }
    }
    return false;
}
int main()
{

    while (scanf("%d%d",&n,&k)!=EOF)
    {
        memset(mat,0,sizeof mat);
        memset(cnt,0,sizeof cnt);
        int a,b;
        for (int i=0;i<k;i++){
            scanf("%d%d",&a,&b);
            mat[a][cnt[a]++]=b;
        }
        memset(lefts,-1,sizeof lefts);
        int ans=0;
        for (int i=1;i<=n;i++){
            memset(vis,0,sizeof vis);
            if (match(i)) ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}

 


联系
我们