2018南京区域赛-Problem I. Magic Potion

2018南京区域赛-Problem I. Magic Potion

There are n heroes and m monsters living in an island. The monsters became very vicious these days,
so the heroes decided to diminish the monsters in the island. However, the i-th hero can only kill one
monster belonging to the set Mi
. Joe, the strategist, has k bottles of magic potion, each of which can buff
one hero’s power and let him be able to kill one more monster. Since the potion is very powerful, a hero
can only take at most one bottle of potion.
Please help Joe find out the maximum number of monsters that can be killed by the heroes if he uses the
optimal strategy.
Input
The first line contains three integers n, m, k (1 ≤ n, m, k ≤ 500) — the number of heroes, the number of
monsters and the number of bottles of potion.
Each of the next n lines contains one integer ti
, the size of Mi
, and the following ti
integers
Mi,j (1 ≤ j ≤ ti), the indices (1-based) of monsters that can be killed by the i-th hero
(1 ≤ ti ≤ m, 1 ≤ Mi,j ≤ m).
Output
Print the maximum number of monsters that can be killed by the heroes.
Examples
standard input standard output
3 5 2
4 1 2 3 5
2 2 5
2 1 2
4
5 10 2
2 3 10
5 1 3 4 6 10
5 3 4 6 8 9
3 1 9 10
5 1 3 6 7 10

***题意***有n个英雄m个怪兽k瓶药水，第i个英雄只能打第i行的怪兽种类，每个英雄一开始有一次机会打倒怪兽，每个英雄最多喝一瓶药水，喝药水可以让英雄再打倒一只怪兽，问最多能打倒几只怪兽。
***思路***看到这个题目就发现是最大流的模板题，先建一个原点跟英雄相连，流量为1，再在英雄和怪兽之间建通道如果这个英雄能打这种怪兽就建立一条1流量的路，最后把所有的怪兽得到的流量汇总到一个汇点，跑一遍最大流，最终的答案就是没有使用药剂时候的最优值ans1，然后假装给所有英雄配一瓶药水，在在原来的基础上再跑一边最大流(因为跑过一遍原先被打过的怪兽的通道都已经用过，所以直接再跑一遍就行了)，得到ans1，跟魔药数量进行比较，取小，最终答案就是ans+min(ans1,k);

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 1000010, E = 2000010;
int vis[N];
int n, m, s, t; LL ans = 0;
LL cnt = 1, first[N], nxt[E], to[E], val[E];
inline void addE(int u, int v, LL w) {
	to[++cnt] = v;
	val[cnt] = w;
	nxt[cnt] = first[u];
	first[u] = cnt;
}
int dep[N], q[N], l, r;
bool bfs() {
	memset(dep, 0, (n + 1) * sizeof(int));

	q[l = r = 1] = s;
	dep[s] = 1;
	while(l <= r) {
		int u = q[l++];
		for(int p = first[u]; p; p = nxt[p]) {
			int v = to[p];
			if(val[p] and !dep[v]) {
				dep[v] = dep[u] + 1;
				q[++r] = v;
			}
		}
	}
	return dep[t];
}
LL dfs(int u, LL in) {
	if(u == t)
		return in;
	LL out = 0;
	for(int p = first[u]; p and in; p = nxt[p]) {
		int v = to[p];
		if(val[p] and dep[v] == dep[u] + 1) {
			LL res = dfs(v, min(val[p], in));
			val[p] -= res;
			val[p ^ 1] += res;
			in -= res;
			out += res;
		}
	}
	if(out == 0)
		dep[u] = 0;
	return out;
}
int main() {
	LL a,b,k;
	scanf("%lld%lld%lld",&a,&b,&k);
	n=a+b+2;
	s=a+b+1;
	t=a+b+2;
	for(int i=1;i<=a;i++)
	{
		addE(s,i,1);
		addE(i,s,0);
	}
	int cc=0;
	for(int i=1;i<=a;i++)
	{
		int t;
		scanf("%d",&t);
		for(int j=1;j<=t;j++)
		{
			int u, v, w;
			u=i;
			scanf("%d",&v);
			if(vis[v]==0)
			{
				vis[v]=1;
				cc++;
			}
			v+=a;
			addE(u, v, 1);
			addE(v, u, 0);
		}
	}
	for(int i=1+a;i<=a+b;i++)
	{
		addE(i,t,1);
		addE(t,i,0);
	}
	while(bfs())
		ans += dfs(s, 1e18);
	for(int p = first[s]; p; p = nxt[p]) 
	{
		val[p]=1;
	}
	LL ans1=0;
	while(bfs())
		ans1 += dfs(s, 1e18);
	if(ans1>=k)
		printf("%lld\n", ans+k);
	else
		printf("%lld\n",ans+ans1);
	return 0;
}