蒟蒻求助,网络流板子(Dinic) 91points #9 TLE

P3376 【模板】网络最大流

无尽星空 @ 2020-08-10 16:15:53

#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 也不对劲


by JimmyFlower @ 2020-08-10 16:17:20

@无尽星空 用当前弧优化


by JimmyFlower @ 2020-08-10 16:20:13

?多加了一个测试点我才发现


by 无尽星空 @ 2020-08-10 16:22:59

用了啊


by 无尽星空 @ 2020-08-10 16:23:24

@JimmyFlower now[x]


by JimmyFlower @ 2020-08-10 16:25:33

@JimmyFlower 噢抱歉,我打的方式不太一样没看见


by RainFestival @ 2020-08-10 16:34:36

@无尽星空

if (!lft) break;

by 无尽星空 @ 2020-08-10 16:46:04

找到原因了:

加当前弧优化:810ms

不加当前弧优化:75ms

!!!

令人谔谔。

……

ps:我是不是学了个fake的当前弧优化

pps:可是我照着蓝书上打的啊


by 无尽星空 @ 2020-08-10 16:46:25

感谢各位大佬


by WGNJF @ 2020-08-10 16:48:35

@无尽星空 ...就离谱


by JimmyFlower @ 2020-08-10 16:51:32

@无尽星空 hh才发现是now的位置放错了


| 下一页