蒟蒻求助10pts dinic
查看原帖
蒟蒻求助10pts dinic
265037
UntilR楼主2021/2/25 17:43

只对了#3

求大佬帮忙,感激不尽。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
queue<int> line;
struct side
{
	int to,next;
	ll wei;
}a[1000001];
int s[500001],n1,n2,n3,m,d[500001],cnt=1,t,cur[500001];
ll ans;
inline void mem(int q,int w,ll e)
{
	a[++cnt].to=w;
	a[cnt].next=s[q];
	s[q]=cnt;
	a[cnt].wei=e;
	return;
}
inline bool bfs()
{
	memcpy(cur,s,sizeof(s));
	memset(d,0,sizeof(d));
	while(!line.empty())
		line.pop();
	d[0]=1;
	line.push(0);
	while(!line.empty())
	{
		int x=line.front();
		line.pop();
		int w=s[x];
		while(w)
		{
			if(d[a[w].to]==0&&a[w].wei!=0)
			{
				d[a[w].to]=d[x]+1;
				line.push(a[w].to);
				if(a[w].to==t)
					return 1;
			}
			w=a[w].next;
		}
	}
	return 0;
}
inline ll dfs(int x,ll fl)
{
	if(x==t)
		return fl;
	ll re=fl;
	int w=cur[x];
	while(w&&re)
	{
		cur[x]=w;
		if(a[w].wei!=0&&d[a[w].to]==d[x]+1)
		{
			ll z=dfs(a[w].to,min(re,a[w].wei));
			a[w].wei-=z;
			a[w^1].wei+=z;
			re-=z;
		}
		w=a[w].next;
	}
	return fl-re;
}
int main()
{
	std::ios::sync_with_stdio(0);
	cin>>n1>>n2>>n3>>m;
	t=n1*2+n2+n3+1;
	for(int i=1;i<=m;i++)
	{
		int q,w;
		cin>>q>>w;
		w+=n1*2;
		mem(w,q,1);
		mem(q,w,0);
	}
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		int q,w;
		cin>>q>>w;
		q+=n1;
		w+=(n1*2+n2);
		mem(q,w,1);
		mem(w,q,0);
	}
	for(int i=1;i<=n1;i++)
		mem(i,i+n1,1),mem(i+n1,i,0);
	for(int i=1;i<=n2;i++)
		mem(0,i+n1*2,0x7f7f7f),mem(i+n1*2,0,0);
	for(int i=1;i<=n3;i++)
		mem(i+n1*2+n2,t,0x7f7f7f),mem(t,i+n1*2+n2,0);
	while(bfs())
		ans+=dfs(0,0x7f7f7f);
	cout<<ans;
	return 0;
}
2021/2/25 17:43
加载中...