题目描述

核心：在二分图中，最小覆盖点=最大匹配数
匈牙利思想：find(x)
及找x的邻点，在邻接表里存的相当于int i=h[x]
在邻接矩阵里则是g[x][i],其中x为第一组里的点，i为第二组里的点

注意：在建图时只要建立一组连向另一组的有向边，不需要双向add

用邻接矩阵来存图

有个小坑，在find函数里，要先判断g[a][b] 再判断st，不然会爆内存

#include <iostream>
#include <cstring>

using namespace std;


int n,m,k;
const int N=110;

int g[N][N],st[N],match[N];

int find(int x)
{
    //遍历x的所有邻点,i是第二组的点,match[i]返回的是第一组的点
    for(int i=1;i<m;i++)
    {
        if(g[x][i] && st[i]==0)
        {
            st[i]==1;
            int t=match[i];
            if(t==0 || find(t)) 
            {
                match[i]=x;
                return 1;
            }
        }
    }

    return 0;
}

int main()
{

    while(cin>>n,n)
    {
        cin>>m>>k; 
        memset(g,0,sizeof g);
        memset(match,0,sizeof match);

        while(k--)
        {
            int id,a,b;
            cin>>id>>a>>b;
            //编号为0的可以直接做掉
            if(!a || !b) continue;
            g[a][b]=1;
        }
        int res=0;
        for(int i=1;i<n;i++)
        {
            memset(st,0,sizeof st);
            if(find(i)) res++;
        }
        cout<<res<<endl;
    }

    return 0;
}

二刷

每个任务可以看出a-b连的一条边，做完某个任务可以看做选择这条边上的任意一个点
问题转化为最小点覆盖问题
二刷注意的问题
1. 匈牙利算法还是不熟练，要先判断st，在!st的情况下判断match

#include <iostream>
#include <cstring>

using namespace std;

const int N=5050;
int e[N],ne[N],st[N],match[N];
int h[N];
int idx;
int n,m,k;

void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

int find(int u)
{
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!st[j])
        {
            st[j]=1;
            if(!match[j] || find(match[j]))
            {
                match[j]=u;
                return 1;
            }
        }

    }

    return 0;
}

int main()
{
    while(cin>>n,n)
    {
        cin>>m>>k;
        memset(h,-1,sizeof h);
        memset(match,0,sizeof match);
        for(int i=1;i<=k;i++)
        {
            int a,b,c;
            cin>>a>>b>>c;
            if(b==0||c==0) continue;
            add(b,c);
        }

        //找最小点覆盖=找最大匹配数
        int res=0;
        for(int i=1;i<=n-1;i++)
        {
            memset(st,0,sizeof st);
            if(find(i)) res++;
        }
        cout<<res<<endl;
    }
    return 0;
}

最大匹配数=最小点覆盖！！！

又忘又忘又忘。
复习完一遍后，很顺利的ac了。
把一个任务的两个编号看做是a向b的一条单向边，问题转化为求最小点覆盖数量，即最大匹配数

#include <iostream>
#include <cstring>

using namespace std;

const int N=100010; 
int n,m,k;
int e[N],ne[N],h[N],idx;
int st[N],match[N];

void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

int find(int u)
{
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(st[j]) continue;
        st[j]=1;
        if(!match[j] || find(match[j]))
        {
            match[j]=u;
            return 1;
        }
    }
    return 0;

}

int main()
{
    while(cin>>n>>m>>k,n)
    {
        memset(h,-1,sizeof h);
        memset(match,0,sizeof match);
        idx=0;

        //把一个任务看做是A向B连的一条单向边
        //求最小点覆盖，即最大匹配
        for(int i=1;i<=k;i++)
        {
            int a,b,c;
            cin>>a>>b>>c;
            if(b==0 || c==0) continue;
            add(b,c);
        }
        int cnt=0;
        for(int i=1;i<=n;i++)
        {
            memset(st,0,sizeof st);
            if(find(i)) cnt++;
        }
        cout<<cnt<<endl;;
    }
    return 0;
}