50 years, 50 colors HDU

//判断每个气球需要多少次才能扎破
//大于k的,那么就不满足条件
//可以看作最小点覆盖问题
//分为两个集合,横坐标集合,纵坐标集合
//然后每个点的坐标在这两个集合中且两点之间有连线
//然后就是求最小点覆盖 
#include<iostream>
#include<cstring>
#include<stdio.h>
#include<math.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn = 105;
int n, k;
int g[maxn][maxn];
int color[52];
bool st[maxn];
int match[maxn];
int nowcolor;
vector<int>v;
void init() {
	memset(g, 0, sizeof(g));
	memset(color, 0, sizeof(color));
	v.clear();
}
bool find(int x) {
	for (int i = 1; i <= n; ++i) {
		if (g[x][i] == nowcolor && st[i] == 0) {
			st[i] = 1;
			if (match[i] == -1 || find(match[i])) {
				match[i] = x;
				return true;
			}
		}
	}
	return false;
}
int solve(int color) {
	nowcolor = color;
	memset(match, -1, sizeof(match));
	int ans = 0;
	for(int i = 1; i <= n; ++i) {
		memset(st, 0, sizeof(st));
		if (find(i))
			ans++;
	}
	return ans;
}
int main() {
	while(~scanf("%d%d", &n, &k) && n && k) {
		init();
		for (int i = 1; i <= n; ++i) 
			for (int j = 1; j <= n; ++j) 
			{	
				scanf("%d", &g[i][j]);
				color[g[i][j]] = 1;
			}
		for(int i = 1; i <= 50; ++i) 
			if (color[i] == 1) 
				if(solve(i) > k) 
					v.push_back(i);
		if (v.size() == 0)
			printf("-1");
		else {
			for(int i = 0; i < v.size(); ++i) {
				if(i) 
					printf(" ");
				printf("%d", v[i]);
			}
		}
		printf("
");
	}
	return 0;
}
原文地址:https://www.cnblogs.com/QingyuYYYYY/p/12401037.html