hdu 1498 二分图—最小点覆盖

题目大意：有 n*n 的矩阵中放着 1-50 种气球，每次只能毁掉一行或者一列。求 k 此操作后那些气球不能被全部毁掉。

解题思路：对于每一种给定的color，当 map[i][j] = color 时可以认为存在一条 i—j 的路径，这样就可以构建一个二分图，二分图的两个点集分别是该颜色气球的横纵坐标；毁掉该 colo r的所有气球所需的次数就是该二分图的最小点覆盖。

什么是图的点覆盖

[cpp]
#include<stdio.h>
#include<string.h>
#define M 105
#define N 55
int map[M][M],link[M],flag[M],ans[N],n,k;   //注意：link和flag数组长度应该和矩阵的行列数相等；
int find(int i,int color)
{
    int j;
    for(j=1;j<=n;j++){
        if(map[i][j]==color&&flag[j]==0){
            flag[j]=1;
            if(link[j]==0||find(link[j],color)==1){
                link[j]=i;
                return 1;
            }
        }
    }
    return 0;
}
int getnum(int color)
{
    int i,sum;
    memset(link,0,sizeof(link));
    for(i=1,sum=0;i<=n;i++){
        memset(flag,0,sizeof(flag));
        if(find(i,color)==1)
            sum++;
    }
    return sum;
}
int main()
{
    int i,j,t;
    while(scanf("%d%d",&n,&k),n||k){
        memset(map,0,sizeof(map));
        memset(ans,0,sizeof(ans));
        for(i=1;i<=n;i++){
            for(j=1;j<=n;j++){
                scanf("%d",&map[i][j]);
            }
        }
        for(i=1,t=0;i<=50;i++){     //注意这里是遍历每一种颜色，所以循环次数等于所有颜色数
            if(getnum(i)>k)
                ans[t++]=i;
        }
        if(t==0)
            printf("-1\n");
        else{
            for(i=0;i<t;i++){
                printf(i==0?"%d":" %d",ans[i]);
            }
            printf("\n");
        }
    }
    return 0;
}

#include<stdio.h>
#include<string.h>
#define M 105
#define N 55
int map[M][M],link[M],flag[M],ans[N],n,k;   //注意：link和flag数组长度应该和矩阵的行列数相等；
int find(int i,int color)
{
int j;
for(j=1;j<=n;j++){
  if(map[i][j]==color&&flag[j]==0){
   flag[j]=1;
   if(link[j]==0||find(link[j],color)==1){
    link[j]=i;
    return 1;
   }
  }
}
return 0;
}
int getnum(int color)
{
int i,sum;
memset(link,0,sizeof(link));
for(i=1,sum=0;i<=n;i++){
  memset(flag,0,sizeof(flag));
  if(find(i,color)==1)
   sum++;
}
return sum;
}
int main()
{
int i,j,t;
while(scanf("%d%d",&n,&k),n||k){
  memset(map,0,sizeof(map));
  memset(ans,0,sizeof(ans));
  for(i=1;i<=n;i++){
   for(j=1;j<=n;j++){
    scanf("%d",&map[i][j]);
   }
  }
  for(i=1,t=0;i<=50;i++){     //注意这里是遍历每一种颜色，所以循环次数等于所有颜色数
   if(getnum(i)>k)
    ans[t++]=i;
  }
  if(t==0)
   printf("-1\n");
  else{
   for(i=0;i<t;i++){
    printf(i==0?"%d":" %d",ans[i]);
   }
   printf("\n");
  }
}
return 0;
}

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