2018-2019 ICPC南京赛区I.Magic Potion（网络流-最大流）

题目：I.Magic Potion

题意

给出n个英雄和m个怪兽，第i个英雄可以从自己可击败属于mi集合的怪兽中的一个。现有k瓶药水，每瓶药水都可以让任意一个英雄多几百一个人怪兽。问最多可以击败多少个怪兽。

题解

求最大流，1——m个怪物重新设置序号为1+n——1+n+m的结点,1——n个勇士重新设置序号为2——1+n的结点，源点序号为0，汇点序号为h=n+m+2。勇士向怪物连边，并设置流量上限为1。源点向每个勇士连边，并设置流量上限为1。设置一个序号为1的虚拟节点，源点连到虚拟结点，流量上限为k，虚拟节点流向每一个勇士，流量上限为1。每个怪物向汇点连边，流量上限为1（假设每个怪兽死一次，实际设置多少没有影响）。

ac代码：

#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define M_PI 3.14159265358979323846
int M[1005][1005],pre[1005],flow[1005];
int bfs(int s,int e)
{
	queue<int>q;
	q.push(s);
	memset(pre,-1,sizeof(pre));
	flow[s]=0x3f3f3f3f;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int v=0;v<=e;v++)
		{
			if(M[u][v]&&pre[v]==-1)
			{
				pre[v]=u;
				flow[v]=min(flow[u],M[u][v]);
				q.push(v);
			}
		}
	}
	if(pre[e]==-1) return -1;//找不到增广路 
	else return flow[e];
}
int maxflow(int s,int e)
{
	int delt,res=0;
	while((delt=bfs(s,e))!=-1)
	{
		int k=e,last=pre[k];
		while(k!=s)
		{
			M[last][k]-=delt;
			M[k][last]+=delt;
			k=pre[k];
			last=pre[k];
		}
		res+=delt;
	}
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	int n,m,k;
	cin>>n>>m>>k;
	int h=n+m+2;
	M[0][1]=k;//源点与虚拟节点相连，流量设置为k
	for(int i=1;i<=n;i++) M[0][i+1]=1,M[1][i+1]=1;//源点连向所有勇士，流量设为1，虚拟节点连向所有的勇士，流量为1
	for(int i=1;i<=m;i++) M[n+i+1][h]=1;//所有怪兽节点连向汇点，流量设置为1
	for(int i=1;i<=n;i++)
	{
		int t,x;
		cin>>t;
		for(int j=0;j<t;j++)
		{
			cin>>x;
			M[i+1][x+n+1]=1;
		}
	} 
	cout<<maxflow(0,h)<<endl;
	return 0;
}