求助
查看原帖
求助
310581
ethan0328楼主2023/8/15 17:03

我的网络流板子能过这题,但是比正常的板子慢将近10倍,自己测了一下发现增广的次数要多将近5,6倍,求帮调。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=210,M=5e3+10;
struct edge
{
	int to,next,mx;
};
int n,m,ind=1,head[N];
edge e[M*2];
int now[N],pos[N];
queue<int> q;
void add(int x,int y,int z)
{
	e[++ind].to=y;
	e[ind].mx=z;
	e[ind].next=head[x];
	head[x]=ind;
}
bool bfs(int s,int t)
{
	int x;
	memset(pos,0,sizeof(pos));
	while(!q.empty())
	{
		q.pop();
	}
	q.push(s);
	pos[s]=1;
	while(!q.empty())
	{
		x=q.front();
		q.pop();
		for(int i=head[x];i;i=e[i].next)
		{
			if(e[i].mx&&!pos[e[i].to])
			{
				pos[e[i].to]=pos[x]+1;
				q.push(e[i].to);
				if(e[i].to==t)
				{
					return 1;
				}
			}
		}
	}
	return 0;
}
int dfs(int x,int flow,int t)
{
	if(x==t)
	{
		return flow;
	}
	int rest=flow,p,y;
	for(;now[x]&&rest;now[x]=e[now[x]].next)
	{
		p=now[x];
		if(e[p].mx&&pos[e[p].to]==pos[x]+1)
		{
			y=dfs(e[p].to,min(e[p].mx,rest),t);
			if(!y)
			{
				pos[e[p].to]=0;
			}
			e[p].mx-=y;
			e[p^1].mx+=y;
			rest-=y;
		}
	}
	return flow-rest;
}
int dinic(int s,int t)
{
	int ret=0,x;
	while(bfs(s,t))
	{
		for(int i=1;i<=n;i++)
		{
			now[i]=head[i];
		}
		while(true)
		{
			x=dfs(s,2e9,t);
			if(!x)
			{
				break;
			}
			ret+=x;
		}
	}
	return ret;
}
signed main()
{
	int x,y,z,s,t;
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++)
	{
		cin>>x>>y>>z;
		add(x,y,z);
		add(y,x,0);
	}
	cout<<dinic(s,t);
}
2023/8/15 17:03
加载中...