hdu 1498 50 years, 50 colors （二分匹配）

题意：
 给你一个n*n的矩阵,在矩阵中分布着s种颜色的气球,给你k次扎破气球
 的操作,每次操作可以扎破一行,或一列的同一颜色的气球。问在k次操
 作后有那几种颜色的气球是不能被完全扎破的.
解题：
  利用二分图匹配,寻找每一种颜色对应的最大匹配(行和列分别为A集合,B集合;M[i,j]代表一个搭配),
  如果大于k则输出"-1",否则输出颜色的递增序列
注：在二分图中求最少的点，让每条边都至少和其中的一个点关联，这就是
二分图的“最小顶点覆盖”。 
[csharp]
#include"stdio.h" 
#include"string.h" 
#include"stdlib.h" 
int map[101][101],mark[101]; 
int v[101],link[101]; 
int a[101],color[101]; 
int k,n; 
int cmp(const void*a,const void*b) 
{ 
    return *(int*)a-*(int*)b; 
} 
int dfs(int i,int k) 
{ 
    int j; 
    for(j=1;j<=n;j++) 
    { 
        if(map[i][j]==k&&!v[j]) 
        { 
            v[j]=1; 
            if(link[j]==0||dfs(link[j],k)) 
            { 
                link[j]=i; 
                return 1; 
            } 
        } 
    } 
    return 0; 
} 
int main() 
{ 
    int i,j,t,tt,ans; 
    while(scanf("%d%d",&n,&k)!=-1) 
    { 
        if(n==0&&k==0) 
            break; 
        memset(color,0,sizeof(color)); 
        memset(mark,0,sizeof(mark)); 
        t=0; 
        for(i=1;i<=n;i++) 
        { 
            for(j=1;j<=n;j++) 
            { 
                scanf("%d",&map[i][j]); 
                if(!mark[map[i][j]]) 
                { 
                    mark[map[i][j]]=1; 
                    color[t++]=map[i][j]; 
                } 
            } 
        } 
        tt=0; 
        for(i=0;i<t;i++) 
        { 
            ans=0; 
            memset(link,0,sizeof(link)); 
            for(j=1;j<=n;j++) 
            { 
                memset(v,0,sizeof(v)); 
                if(dfs(j,color[i])) 
                    ans++; 
            } 
            if(ans>k) 
                a[tt++]=color[i]; 
        } 
        if(tt==0) 
            printf("-1\n"); 
        else www.zzzyk.com
        { 
            qsort(a,tt,sizeof(a[0]),cmp); 
            for(i=0;i<tt-1;i++) 
                printf("%d ",a[i]); 
            printf("%d\n",a[i]); 
        } 
    } 
    return 0; 
} 
作者：yyf573462811

补充：软件开发 , C++ ,