hdu1498最小点覆盖

1.题意：(很是重要，理解了题意才能有转换为最小点覆盖的思路)，对于一个n*n的矩阵，里面有一些颜色不同的气球(用1~50标记种类)，给你K次机会，每次机会可以把某一行或者某一列中的某一种颜色全部消灭，问你K次消灭之后，有哪些颜色是你不能消灭完的....拿题目的案例 2 来画图：

我们这里只有K=1次机会去消除,,我们只有四种方式，从图中来看，1次机会我们不可能把1号颜色全部消除，但是有能把2号颜色消除的情况

2.分析：那么对于题目，我们的解决方案就是要把图中所有的颜色枚举一次，比如枚举 i 号颜色，那么就先求出全部消除 i 号颜色要用到的最小次数，那么对于求解这次最小次数...我们就考虑用到二分匹配匈牙利算法，并且是一个“最小点覆盖”的思路

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define MAX 101

int n,k;
int map[MAX][MAX];//存放整个图 map[i][j]的值 就是该方格的颜色
int link[MAX];
bool color[MAX],vis[MAX];//color[i] 为真 表示i号颜色在整个map中出现

bool dfs(int i,int co)//本次dfs过程中 是用 第i行 颜色为 co 去匹配，
{
for(int j = 0; j < n; j ++)
{
if(!vis[j] && map[i][j] == co)
{
vis[j] = true;
if(link[j] == -1 || dfs(link[j],co))
{
link[j] = i;return true;
}
}
}
return false;
}

int KM(int co)
{
memset(link,-1,sizeof(link));
int ans=0;
for(int i = 0; i < n ; i ++)
{
memset(vis,false,sizeof(vis));
if(dfs(i,co)) ans++;
}
return ans;
}

int main()
{
int i,j;
int ans[51],tol;//ans[] 存放的是要输出的不能消灭的颜色号，tol表示不能消灭的颜色数量
while(scanf("%d%d",&n,&k),n+k)
{
memset(color,false,sizeof(color));
memset(map,0,sizeof(map));
for(i = 0; i < n; i ++)
{
for(j = 0; j < n; j ++)
{
scanf("%d",&map[i][j]);
color[map[i][j]] = true;
}
}
tol=0;
for(i = 1; i <= 50; i ++)
{
if(color[i])//注意这里表示 i 号颜色是不是有的
{
if(KM(i) > k)//如果匹配最小消除i号颜色用到的次数大于k 意思就是不能消灭
ans[tol++]=i;
}
}
sort(ans,ans+tol);//注意排序
if(tol == 0)
printf("-1");
else
for(i = 0; i < tol; i ++)
i == 0 ? printf("%d",ans[i]):printf(" %d",ans[i]);//这里是简单的格式控制，两数据中有空格
printf("\n");
}
return 0;
}