題意：
給你一個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.2cto.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
