Hdu1498 50 years, 50 colors 【最小点覆盖】

本文主要是介绍Hdu1498 50 years, 50 colors 【最小点覆盖】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

50 years, 50 colors

题意

有一个 $\times n$ 的方阵，每一个格子里面有某种颜色的气球，颜色编号范围是： $[1, 50]$
允许 $k$ 次操作，每次操作可以选择一行或一列，将位于那行或那一列的某种颜色的气球全部撞破
问对于每种颜色的气球，能否在 $k$ 次操作内全部撞破？

思路

对于当前考虑的颜色，提前将其所有坐标存储起来；对于某个坐标 $(r, c)$ ，我们一定要选择 $r$ 这一行或 $c$ 这一列，
不妨将每一行抽象成点，每一列也抽象成点，将坐标 $(r, c)$ 抽象成行列之间的边，那么问题就转化成了：最多选择 $k$ 个点，覆盖所有边，也即是求最小点覆盖

判断最小点覆盖点集大小是否大于 $k$ 即可

// Problem: 50 years, 50 colors
// Contest: HDOJ
// URL: https://acm.hdu.edu.cn/showproblem.php?pid=1498
// Memory Limit: 32 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
#define fore(i,l,r)	for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n' 
#define ull unsigned long longconst int INF=0x3f3f3f3f;
const long long INFLL=0x3f3f3f3f3f3f3f3fLL;typedef long long ll;const int M = 50;std::vector<std::pair<int, int>> ball[M + 5];
std::vector<std::vector<int>> g;
std::vector<bool> used;
std::vector<int> match;bool dfs(int u){for(auto v : g[u])if(!used[v]){used[v] = true;if(!match[v] || dfs(match[v])){match[v] = u;return true;}}return false;
}int main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int n, k;while(std::cin >> n >> k && n && k){std::vector<std::vector<int>> a(n + 1, std::vector<int>(n + 1));fore(i, 1, M + 1)	ball[i].clear();fore(i, 1, n + 1)fore(j, 1, n + 1){std::cin >> a[i][j];ball[a[i][j]].push_back({i, j});}std::vector<int> ans;fore(color, 1, M + 1){if(ball[color].empty())	continue;g.assign(n + 1, std::vector<int>());match.assign(n + 1, 0);for(auto [r, c] : ball[color])	g[r].push_back(c);int cnt = 0;fore(r, 1, n + 1){used.assign(n + 1, false);cnt += dfs(r);}if(cnt > k)	ans.push_back(color);}if(ans.empty())	std::cout << "-1\n";else{for(auto x : ans)	std::cout << x << ' ';	std::cout << endl;}}return 0; 
}