(最大流,二分图的多重匹配) Magic Potion

(最大流,二分图的多重匹配) Magic Potion
题意:n个人,m个怪物,k瓶药水,每个人可以打死对应的集合里面的一个怪物,一碰药水可以让一个人多打死一个怪物,每个人最多只能用一瓶药水,问最多能打死多少个怪物
思路:想到了匹配,然后用最大流做,一开始想的建图是从超级原点连一条容量是n+k的边到虚拟节点,然后虚拟节点与所有勇士连一条容量是2的边,然后勇士与对应的怪物连1的边,怪物与汇点连1的边跑最大流,然后wa了,错误在于我们这样做默认勇士可以用药了,然后k等于0的时候,答案就不对了,所以正解是超级源点和所有勇士连1的边,药水节点与勇士连1的边,超级源点与药水连k的边,勇士和对应怪物连1的边,怪物与汇点连1的边,跑最大流
ac代码:

#include<iostream>
#include<cstring>
using namespace std;
const int N=10000,M=60010;
int h[N],ne[M],e[M],idx,f[M];
void add(int a,int b,int c)
{
	e[idx]=b,ne[idx]=h[a],f[idx]=c,h[a]=idx++;
	e[idx]=a,ne[idx]=h[b],f[idx]=0,h[b]=idx++;
}
const int INF=1e8;
int S0,S,T,n,m,k;
int d[N];
int cur[N];
int q[N];
int bfs()
{
	int hh=0,tt=0;
	memset(d,-1,sizeof d);
	//cout<<S<<endl;
	d[S]=0;
	cur[S]=h[S];
	q[0]=S;
	while(hh<=tt)
	{
		int t=q[hh++];
		for(int i=h[t];~i;i=ne[i])
		{
			int j=e[i];
			if(f[i]&&d[j]==-1)
			{
				d[j]=d[t]+1;
				cur[j]=h[j];
				if(j==T)	return true;
				q[++tt]=j;
			}
		}
	}
	return false;
}	
int dfs(int u,int limit)
{
	//cout<<u<<endl;
	if(u==T)
		return limit;
	int flow=0;
	for(int i=cur[u];~i&&flow<limit;i=ne[i])
	{
		int j=e[i];
		cur[u]=i;
		if(d[j]==d[u]+1 && f[i])
		{
			int t=dfs(j,min(f[i],limit-flow));
			if(!t)
			d[j]=-1;
			f[i]-=t;
			flow+=t;
			f[i^1]+=t;
		}
	}
	return flow;
}
int dinic()
{
	int res=0,flow;
	while(bfs())
	while(flow=dfs(S,INF))
	res+=flow;
	return res;
}
int main()
{
	cin >> n >> m >> k;
	//cout<<n<<' '<<m<<' '<<k<<endl;
	memset(h,-1,sizeof h);
	for(int i=1;i<=n;i++)
	{
		int t;
		cin>>t;
		while(t--)
		{
			int x;
			cin>>x;
			add(i,n+x,1);
		}
	}
	for(int i=1;i<=n;i++)
		add(n+m+1,i,1),add(0,i,1);
	for(int i=n+1;i<=n+m;i++)
		add(i,n+m+2,1);
		add(0,n+m+1,k);
		S=0;
		T=n+m+2;
		cout<<dinic()<<endl;
}

 

上一篇:【LEETCODE】55、数组分类,适中级别,题目:79、611、950


下一篇:potion