题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1498
/*
题意：
给你一个n*n的矩阵,在矩阵中分布着s种颜色的气球,给你k次扎破气球
的操作,每次操作可以扎破一行,或一列的同一颜色的气球。问在k次操
作后有那几种颜色的气球是不能被完全扎破的.
解题思路：
使用二部图最大匹配，寻找每种颜色的最大匹配数，（行，列分别为两个匹配）
如果都在m次内可以被刺破，则输出 -1 否则的话，按不能被刺破的气球
编号从小到大进行输出。
*/
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define maxn 101
int map[maxn][maxn],n,m,color[maxn],vis[maxn],mark[maxn],cb[maxn];
bool dfs(int k,int v)
{
for(int i = 1; i <= n; i++)
{
if(map[i][v] != k || vis[i])
continue;
vis[i] = 1;
if(!mark[i] || dfs(k,mark[i]))
{
mark[i] = v;
return true;
}
}
return false;
}
int cmp(const void *a ,const void *b)
{
return (int *)a - (int *)b;
}
int main()
{
int i,j,ans,num,color_num;
while(~scanf("%d%d",&n,&m) && (n||m))
{
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n; j++)
{
scanf("%d",&map[i][j]);
}
}
num = 0;
for(i = 1; i <= 50; i++)
{
ans = 0;
memset(mark,0,sizeof(mark));
for(j = 1; j <= n; j++)
{
memset(vis,0,sizeof(vis));
if(dfs(i,j))
ans++;
}
if(ans > m)
cb[num++] = i;
}
if(num == 0)
printf("-1\n");
else
{
qsort(cb,num,sizeof(int),cmp);
for(i = 0; i < num - 1; i++)
printf("%d ",cb[i]);
printf("%d\n",cb[i]);
}
}
return 0;
}