HDU 1498 50 years,50 colors

题意

n*n的矩形中放入颜色值为[1,50]的气球，要求每一个人扎k次，每扎一次，可将同行或者同列相同颜色的气球全部扎破。求是否存在不可能全部扎破的气球，按照升序规律输出气球的颜色。

思路

每种颜色进行最小点覆盖运算，如果最小覆盖点num>k，则该颜色气球不能全部扎破。 矩形行列分别为集合A和集合B，如果判断颜色k气球，则如果map [i] [j] = k，则表示存在一条边，这样便可以转换成最小点覆盖问题，只需要找出最小的点，清除掉两集合之间所有的边即。

代码

#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int N = 105; int map[N][N]; //气球的总图 int link[N]; //link[j]:第j列被扎过时，扎的气球位置的行(无则-1) int useif[N]; //第i列是否被扎过 int ans[N]; //记录不能全部扎破的气球，ans[i]为某颜色数值 int len; int n, k; int dfs(int t, int col) { for(int i = 0; i < n; i++) { if(!useif[i] && map[t][i] == col) { useif[i] = 1; //寻找增广路，如果有增广路，说明该位置需要扎气球 if(link[i] == -1 || dfs(link[i], col)) { link[i] = t;//说明i列被扎过，初始扎的气球位置在t行 return 1; } } } return 0; } int maxMatch(int col) { memset(link, -1, sizeof(link)); int num = 0; for(int i = 0; i < n; i++) { memset(useif, 0, sizeof(useif));//对每一行都要初始化 if(dfs(i, col)) num ++; } return num; } int main() { while(scanf("%d %d", &n, &k) && n && k ) { memset(map, 0, sizeof(map)); len = 0; for(int i = 0; i < n; i++) for(int j=0;j<n;j++) scanf("%d", &map[i][j]); for(int i = 1; i <= 50; i++) { if(maxMatch(i) > k)//每种颜色都判断一次，执行n次最小点覆盖 ans[len ++] = i; } if(!len) printf("-1\n"); else { for(int i=0;i<len-1;i++) printf("%d ", ans[i]); printf("%d\n",ans[len - 1]); } } return 0; }