萌新求助,发现网络流模板T了艹,TLE 90pts

P3376 【模板】网络最大流

Spasmodic @ 2020-08-08 20:55:11

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=205,M=5005,INF=0x3f3f3f3f3f3f3f3f; 
ll n,m,s,t,tot=1,hd[N],d[N],ans;
struct edge{ll t,c,nxt;}es[M<<1];
void add(ll u,ll v,ll c){
    es[++tot]=(edge){v,c,hd[u]};hd[u]=tot;
    es[++tot]=(edge){u,0,hd[v]};hd[v]=tot;
}
bool bfs(){
    memset(d,0,sizeof(d));
    queue<ll>q;
    q.push(s);d[s]=1;
    for(ll x;!q.empty();){
        x=q.front();q.pop();
        for(ll i=hd[x];i;i=es[i].nxt)
            if(es[i].c&&!d[es[i].t]){
                q.push(es[i].t);
                d[es[i].t]=d[x]+1;
                if(es[i].t==t)return 1;
            }
    }
    return 0;
}
ll dinic(ll x,ll flow){
    if(x==t)return flow;
    ll rest=flow,k;
    for(ll i=hd[x];i;i=es[i].nxt)
        if(es[i].c&&d[es[i].t]==d[x]+1){
            k=dinic(es[i].t,min(rest,es[i].c));
            es[i].c-=k,es[i^1].c+=k;
            rest-=k;
        }
    if(flow-rest==0)d[x]=-1;
    return flow-rest;
}
int main(){
    scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
    for(ll i=1,u,v,c;i<=m;i++){
        scanf("%lld%lld%lld",&u,&v,&c);
        add(u,v,c);
    }
    for(ll flow=0;bfs();)while((flow=dinic(s,INF)))ans+=flow;
    printf("%lld",ans);
    return 0;
} 

by 辰星凌 @ 2020-08-08 20:56:24

Orz网络瘤巨佬


by 辰星凌 @ 2020-08-08 20:57:20

当前狐呢?/yiw


by Earthcomputer @ 2020-08-08 20:57:22

Orz网络瘤巨佬


by optimize_2 @ 2020-08-08 20:58:43

Orz网络瘤巨佬


by WaReTle @ 2020-08-08 20:59:00

当前弧优化?


by Spasmodic @ 2020-08-08 21:00:30

草我大概学了个假的当前弧优化

重学当前弧咯


by Spasmodic @ 2020-08-08 21:07:04

好了 63ms艹了祭


by UltiMadow @ 2020-08-08 21:08:44

@happydef

for(ll i=hd[x];i;i=es[i].nxt)

->

for(ll i=hd[x];i&&rest;i=es[i].nxt)

我之前在这倒过(


by Eason_AC @ 2020-08-08 21:15:56

所以说写EK它不香么(


by Spasmodic @ 2020-08-08 21:19:14

@Eason_AC EK慢


| 下一页