题意
给定n个英雄,m个怪兽,k个药水。
每个英雄只能杀死给定集合中的一个怪兽,使用药水后可以多杀一个,每个英雄最多使用一个药水。
https://codeforces.com/gym/101981/problem/I
关键词
二分图匹配、最大流、匈牙利算法、Dinic
思路
- 二分图匹配:将英雄点划分为一个集合,怪兽点划分为一个集合,求两次最大匹配,第一次直接求最大匹配 cnt1,求完后去除第一次最大匹配中的怪兽点,再求一次最大匹配 cnt2,最终结果为 cnt1 + min(k, cnt2)。这样写会一直Wrong answer on test 7,听说原因为:第一求完最大匹配后的图,不一定能求出第二次最大匹配的最优解,需要在第一次求完最大匹配后进行一个排序,较为复杂。
- 最大流:数据量不大,直接邻接矩阵建图,Dinic求最大流。
建图
案例1最大流建图
1 - n表示英雄,n+1 - m+n 表示怪兽, 0表示起点(简称S点), n+m+1表示终点(E点),n+m+2表示K瓶药水所代表的点(K点)。
说明
- 起点 -> K点的边,流量为k,其他边流量为1:象征最多使用k瓶药水。
- K点 -> 英雄点,流量为1:每个英雄最多使用一瓶药水。
- 怪兽点 -> E点,流量为1:每个怪兽最多只能被杀一次。
代码
#include <bits/stdc++.h> #define Debug 0 #define MAXN 1056 #define MAXM 2600 #define MOD 1000000007 #define INF 0x3f3f3f3f #define PI 3.1415926535 #define pb push_back #define SYNC ios::sync_with_stdio(false); //#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt" typedef long long ll; typedef std::pair<int, int> Pair; using namespace std; int n, m, k; int S, E, K; int G[MAXN][MAXN]; int dep[MAXN]; void add_edge (int u, int v, int f) { // 依题意,单向边,双向会WA // G[u][v] = G[v][u] = f; G[u][v] = f; } bool bfs (int s, int e) { memset(dep, -1, sizeof(dep)); queue<int> que; dep[s] = 0; que.push(s); while (!que.empty()) { int u = que.front(); que.pop(); for (int i = 0; i < MAXN; ++i) { int v = i; int flow = G[u][i]; if (v != u && dep[v] == -1 && flow > 0) { dep[v] = dep[u] + 1; que.push(v); } } } return dep[e] != -1; } int dfs (int u, int flow) { if (u == E || flow == 0) { return flow; } int max_flow = 0, find_flow; for (int i = 0; i < MAXN; ++i) { int v = i; int f = G[u][i]; if (v != u && f > 0 && dep[v] == dep[u] + 1) { find_flow = dfs(v, min(flow - max_flow, f)); if (find_flow > 0) { G[u][v] -= find_flow; G[v][u] += find_flow; max_flow += find_flow; if (max_flow == flow) return flow; } } } if (max_flow == 0) dep[u] = -1; return max_flow; } int dinic () { int max_flow = 0; while (bfs(S, E)) { max_flow += dfs(S, INF); } return max_flow; } int main () { #ifdef FILE_IN freopen(FILE_IN, "r", stdin); #endif // SYNC cin >> n >> m >> k; S = 0, E = n + m + 1, K = n + m + 2; memset(G, 0, sizeof(G)); add_edge(S, K, k); for (int i = 1; i <= n; ++i) { add_edge(S, i, 1); add_edge(K, i, 1); int t; cin >> t; for (int j = 0; j < t; ++j) { int v; cin >> v; add_edge(i, n + v, 1); } } for (int i = 1; i <= m; ++i) { add_edge(i + n, E, 1); } int ans = dinic(); cout << ans << endl; #ifdef FILE_IN fclose(stdin); #endif return 0; }