HDU 1498

http://acm.hdu.edu.cn/showproblem.php?pid=1498

最小顶点覆盖，建立二分图求最大匹配

#include <iostream>
#include <cstdio>
#include <map>
using namespace std ;
int M[105][105],k,n,match[505],vis[505],a[105][105],ans[55],mm[55] ;
int find(int s)
{
    for(int i=1 ;i<=n ;i++)
    {
        if(!vis[i] && M[s][i])
        {
            vis[i]=1 ;
            if(match[i]==-1 || find(match[i]))
            {
                match[i]=s ;
                return 1 ;
            }
        }
    }
    return 0 ;
}
int max_match()
{
    int res=0 ;
    memset(match,-1,sizeof(match)) ;
    for(int i=1 ;i<=n ;i++)
    {
        memset(vis,0,sizeof(vis)) ;
        res+=find(i);
    }
    return res;
}
int main()
{
    while(~scanf("%d%d",&n,&k))
    {
        if(!n && !k)break ;
        memset(mm,0,sizeof(mm)) ;
        for(int i=1 ;i<=n ;i++)
        {
            for(int j=1 ;j<=n ;j++)
            {
                scanf("%d",&a[i][j]) ;
                mm[a[i][j]]=1 ;
            }
        }
        memset(M,0,sizeof(M)) ;
        int st=0 ;
        for(int i=1 ;i<=50 ;i++)
        {
            if(mm[i])
            {
                for(int j=1 ;j<=n ;j++)
                {
                    for(int h=1 ;h<=n ;h++)
                    {
                        if(a[j][h]==i)M[j][h]=1 ;
                        else M[j][h]=0 ;
                    }
                }
                int res=max_match() ;
                if(res>k)ans[st++]=i ;
            }
        }
        if(!st)puts("-1") ;
        else{
            for(int i=0 ;i<st ;i++)
            {
                if(i)
                    printf(" %d",ans[i]) ;
                else
                    printf("%d",ans[i]) ;
            }
            putchar('
') ;
        }
    }
    return 0 ;
}