链接:https://vjudge.net/problem/HDU-1498#author=634579757
题意:
撞气球游戏,一个n*n的矩阵中,有不同颜色的气球,气球的颜色最多50种(从1到50)。
游戏开始前,先选择一种颜色。游戏开始后,每次选择一行或者一列包含该种颜色的气球进行撞击。如果选择行,那么这一行的气球都会炸裂。如果选择列,这一列的气球都炸裂。
请你求出,有多少种颜色的气球,无论怎么玩,都不能在K次之内,把所有同色的气球都撞裂。
思路:
二分图匹配, 用set记录所有存在的颜色,然后根据x,y求最大匹配,条件是Map[i][j] == color。
最大匹配大于k即可。
代码:
#include <iostream> #include <memory.h> #include <string> #include <istream> #include <sstream> #include <vector> #include <stack> #include <algorithm> #include <map> #include <queue> #include <math.h> #include <cstdio> #include <set> #include <iterator> #include <cstring> using namespace std; typedef long long LL; const int MAXN = 2000+10; vector<int> G[MAXN]; int Map[200][200]; int Link[MAXN], Vis[MAXN]; int n, m, k; int mid; void Init() { for (int i = 1;i <= n;i++) G[i].clear(); } bool Dfs(int x) { for (int i = 1;i <= n;i++) { if (Map[x][i] == mid && Vis[i] == 0) { Vis[i] = 1; if (Link[i] == -1 || Dfs(Link[i])) { Link[i] = x; return true; } } } return false; } int Solve() { memset(Link, -1, sizeof(Link)); int cnt = 0; for (int i = 1;i <= n;i++) { memset(Vis, 0, sizeof(Vis)); if (Dfs(i)) cnt++; } return cnt; } int main() { while (~scanf("%d%d", &n, &m) && n) { set<int> node; memset(Map, 0, sizeof(Map)); for (int i = 1;i <= n;i++) { for (int j = 1;j <= n;j++) { cin >> Map[i][j]; node.insert(Map[i][j]); } } vector<int> Out; for (set<int>::iterator it = node.begin();it != node.end();it++) { mid = *it; int tmp = Solve(); if (tmp > m) Out.push_back(mid); } if (!Out.size()) cout << -1 << endl; else { cout << Out[0]; for (int i = 1;i < Out.size();i++) cout << ' ' << Out[i]; cout << endl; } } return 0; }