HDU1498 二分匹配+最大顶点覆盖

题意：给定一张图，图中的每个数代表一种颜色的气球

求：哪种颜色的气球不能在K次中被消灭（ 每次只能消灭一行或者一列 ）

二分匹配：按照题意来分析 就是要寻找一种消灭方法 使得所有同种气球被消灭 这就符合了最小点覆盖的意义

当所有的点（在这里也就是气球的行号和列号 ） 被覆盖，也就是所有的行号和列号被覆盖

最小点覆盖=最大匹配

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<math.h>
#include<algorithm>
using namespace std;
const int maxn = 55;
const int maxm = 105;
int cnt[ maxn ];
int mat[ maxm ][ maxm ];
void init(){
    memset( cnt,0,sizeof( cnt ) );
    memset( mat,0,sizeof( mat ));
}
int n,k;
int vis[ maxm ],link[ maxm ];
int dfs( int now,int c ){
    //int next;
    for( int i=1;i<=n;i++ ){
        if( vis[ i ]==0&&mat[now][ i ]==c ){
            vis[ i ]=1;
            if( link[ i ]==-1||dfs( link[i],c ) ){
                link[ i ]=now;
                return 1;
            }
        }
    }
    return 0;
}

int km( int c ){
    memset( link,-1,sizeof( link ));
    int ans=0;
    for( int i=1;i<=n;i++ ){
        memset( vis,0,sizeof( vis ));
        ans+=dfs( i,c );
    }
    return ans;
}

int main(){
    while( scanf("%d%d",&n,&k)==2 ,n+k ){
        init();
        for( int i=1;i<=n;i++ ){
            for( int j=1;j<=n;j++ ){
                scanf("%d",&mat[ i ][ j ]);
                cnt[ mat[i][j] ]++;
            }
        }
        int num[ maxn ];
        int CNT=0;
        for( int i=1;i<=50;i++ ){
            if( cnt[ i ]&&km( i )>k ){
                num[ CNT ]=i;
                CNT++;
            }
        }
        if( CNT==0 )
            printf("-1\n");
        else{
            printf("%d",num[0]);
            for( int i=1;i<CNT;i++ )
                printf(" %d",num[ i ]);
            printf("\n");
        }
    }
    return 0;
}