hdu1498最小点覆盖

hdu1498最小点覆盖

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

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

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

#include#include#includeusing namespace std;#define MAX 101int 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;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。