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

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

POJ 1469

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

#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[][],cnt[];

int vis[],lefts[];

int n,k;

bool match(int u)

{

    for (int i=;i<cnt[u];i++){

        int v=mat[u][i];

        if (!vis[v]){

            vis[v]=;

            if (lefts[v]==- || match(lefts[v])){

                lefts[v]=u;

                return true;

            }

        }

    }

    return false;

}

int main()

{

    while (scanf("%d%d",&n,&k)!=EOF)

    {

        memset(mat,,sizeof mat);

        memset(cnt,,sizeof cnt);

        int a,b;

        for (int i=;i<k;i++){

            scanf("%d%d",&a,&b);

            mat[a][cnt[a]++]=b;

        }

        memset(lefts,-,sizeof lefts);

        int ans=;

        for (int i=;i<=n;i++){

            memset(vis,,sizeof vis);

            if (match(i)) ans++;

        }

        printf("%d\n",ans);

    }

    return ;

}

二分图匹配 最大匹配数+最大点覆盖 POJ 1469+POJ 3041的相关教程结束。