蒟蒻求助,网络流板子(Dinic) 91points #9 TLE
查看原帖
蒟蒻求助,网络流板子(Dinic) 91points #9 TLE
179253
无尽星空楼主2020/8/10 16:15
#include<bits/stdc++.h>
#define LL long long
#define R register int
using namespace std;
const int N=205,M=10005;
int n,m,h[N],to[M],nx[M],cnt=1,now[N],d[N],s,t;
LL flow[M],ans,inf=10000000000;
queue<int> q;
void add(int x,int y,int fl) {to[++cnt]=y;flow[cnt]=fl;nx[cnt]=h[x];h[x]=cnt;} 
inline int read()
{
	int s=0;char c=getchar();
	while(!isdigit(c))  c=getchar();
	while(isdigit(c))  s=(s<<3)+(s<<1)+(c^48),c=getchar();
	return s;
}
bool bfs()
{
	int x;
	for(x=1;x<=n;x++)  d[x]=0,now[x]=h[x];
	while(q.size())  q.pop();
	q.push(s);d[s]=1;
	while(q.size())
	{
		x=q.front();q.pop();
		for(R i=h[x];i>1;i=nx[i])
		{
			int y=to[i];
			if(flow[i]&&!d[y])
			{
				q.push(y);
				d[y]=d[x]+1;
				if(y==t)  return 1;
			}
		}
	}
	return 0;
}
inline LL dinic(int x,LL fl)
{
	if(x==t)  return fl;
	LL lft=fl,us;
	int i=now[x];
	for(;i>1&&lft;i=nx[i])
	{
		int y=to[i];
		if(flow[i]&&d[y]==d[x]+1)
		{
			us=dinic(y,min(lft,flow[i]));
			if(!us)  d[y]=0;
			flow[i]-=us;
			flow[i^1]+=us;
			lft-=us;
		}
	}
	now[x]=i;
	return fl-lft;
}
int main()
{
	n=read();m=read();s=read(),t=read();
	while(m--)
	{
		int x=read(),y=read(),z=read();
		add(x,y,z);add(y,x,0);
	}
	LL fl=0;
	while(bfs())
		while(fl=dinic(s,inf))  ans+=fl;
	printf("%lld",ans);
	return 0;
}

附:评测记录

ps:按照题目说法,#10 也不对劲

2020/8/10 16:15
加载中...