ethan0328 @ 2023-08-15 17:03:44
我的网络流板子能过这题,但是比正常的板子慢将近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);
}
by Argvchs @ 2023-08-15 17:24:08
啊不对这里确实错了,不然 now
要多改一次
if ((rest -= y) == 0) break;
by ethan0328 @ 2023-08-15 18:25:23
@Argvchs thx