pku1325 Machine Schedule

#include<stdio.h>

const int Maxn=101;
bool g[Maxn][Maxn],visit[Maxn];
int link[Maxn];
int n,m;

bool find(int x)
{
    for(int i=1;i<=m;i++)
    {
        if(g[x][i]&&!visit[i])
        {
            visit[i]=true;
            if(link[i]==0||find(link[i]))        
            {                                    
                link[i]=x;                        
                return true;
            }                                    
        }
    }
    return false;
}

int main()
{
    int k;
    while(scanf("%d",&n),n)
    {
        scanf("%d%d",&m,&k);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                g[i][j]=false;

        for(int i=1;i<=m;i++)
            link[i]=0;

        for(int i=1;i<=k;i++)
        {
            int v1,v2;
            scanf("%*d%d%d",&v1,&v2);
            g[v1][v2]=true;
        }

        int match=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)        
                visit[j]=false;
            if(find(i))    match++;
        }
        printf("%d\n",match);
    }
    return 0;
}

 

解题思路：

由题意可知，要用最少的点集关联所有的边，即求二分图的最小顶点覆盖。

二分图的最小顶点覆盖=二分图的最大顶点匹配数，具体证明参看Matrix67大牛的证明。