题意
给定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;
}
网友评论