棕名求助
查看原帖
棕名求助
224927
lei_yu楼主2020/7/3 20:06

貌似炸的很惨,一次dfs只能增加1最大流,有没有什么其他的优化?

(打了弧优化的啊)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int head[1000001],cnt,n,m,s,t,maxflow,dis[1000001],ans,vis,cur[1000001],pp,qq;
queue<int>q;
struct node
{
	int to,dis,next;
}a[10000001];
void add_edge(int from,int to,int dis)
{
	a[++cnt].to=to;
	a[cnt].dis=dis;
	a[cnt].next=head[from];
	head[from]=cnt;
}
bool bfs()
{
	//cout<<"bfs"<<endl;
	for(int i=1;i<=n;i++)
	{
		cur[i]=head[i];
		dis[i]=0;
	}
	while(!q.empty())q.pop();
	q.push(s);
	dis[s]=1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=a[i].next)
		{
			int v=a[i].to;
			if(a[i].dis&&!dis[v])
			{
				q.push(v);
				dis[v]=dis[u]+1;
				if(v==t)return 1;
			}
		}
	}
	return 0;
}
int luogu(int u,int flow_now)//返回u点使用了多少流量,flow_now为当前点可以使用的流量 
{	
	//cout<<u<<endl;
	//cout<<"dfs"<<endl;
	if(u==t)
	{
		//vis=1; 
		return flow_now;
	} 
	int k=0,used=0;
	for(int i=cur[u];i;i=a[i].next)
	{
		cur[u]=i;
		int v=a[i].to;
		if(a[i].dis&&dis[v]==dis[u]+1)
		{
			k=luogu(v,min(flow_now-used,a[i].dis));
			if(!k)dis[v]=0;
			a[i].dis-=k;
			a[i^1].dis+=k;
			used+=k;
		}
	}
	return used;
}
int main()
{
	freopen("P1231_2.in","r",stdin);
	freopen("Greg_Tech_No_Hope.txt","w",stdout);
	int x,y;
	cin>>n>>pp>>qq;
	cnt++;
	cin>>m;
	for(int i=1;i<=n;i++)
	{
		add_edge(i,i+n,1);
		add_edge(i+n,i,0);
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		add_edge(y+2*n,x,1);
		add_edge(x,y+2*n,0);
	}
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		add_edge(x+n,y+2*n+pp,1);
		add_edge(y+2*n+pp,x+n,0);
	}
	for(int i=1;i<=pp;i++)
	{
		add_edge(2*n+pp+qq+1,i+2*n,1);
		add_edge(i+2*n,2*n+pp+qq+1,0);
	}
	for(int i=1;i<=qq;i++)
	{
		add_edge(i+2*n+pp,2*n+pp+qq+2,1);
		add_edge(2*n+pp+qq+2,i+2*n+pp,0);
	}
	s=2*n+pp+qq+1;
	t=2*n+pp+qq+2;
	n=2*n+pp+qq+2;
	while(bfs())
	{
		//cout<<"bfs"<<endl;
		while(1)
		{
			//cout<<"dfs"<<endl;
			//vis=0;
			ans=luogu(s,0x7fffffff);
			if(!ans)break;
			maxflow+=ans;
			cout<<maxflow<<endl;
		}
	}
	cout<<maxflow;
}
2020/7/3 20:06
加载中...