为啥EK过了

P3376 【模板】网络最大流

Lates @ 2020-03-15 15:45:57

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue> 
#define _min(a,b) ((a)<(b)?(a):(b))
#define int long long 
using namespace std;
inline int read(){
    register int x=0,f=0,ch=getchar();
    while('0'>ch||ch>'9')f^=ch=='-',ch=getchar();
    while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=getchar();
    return f?-x:x;
}
const int MAX=100005,INF=0x3f3f3f3f;
queue<int>q;
struct E{
    int e,next,w;
}e[MAX<<1];
int cnt=1,head[MAX];
inline void add(int u,int v,int w){
    e[cnt]=(E){v,head[u],w};
    head[u]=cnt++;
}
int res,ans,n,m,x,flow[MAX],pre[MAX],pr[MAX]; 
inline int bfs(int s,int t){
    while(!q.empty())q.pop();
    memset(pre,-1,sizeof(pre));
    memset(pr,0,sizeof(pr));
    pre[s]=0;
    q.push(s);flow[s]=INF;
    while(!q.empty()){
        x=q.front();
        q.pop();
        if(x==t)break;
        for(register int i=head[x];i;i=e[i].next){
            if(e[i].w>0&&pre[e[i].e]==-1){
                pre[e[i].e]=x;
                pr[e[i].e]=i;
                flow[e[i].e]=_min(flow[x],e[i].w);
                q.push(e[i].e);
            }
        }
    }
    return pre[t]==-1?-1:flow[t];
}
inline void EK(int s,int t){
    res=0;
    while((res=bfs(s,t))!=-1){
        x=t;ans+=res;
        while(x!=s){
            e[pr[x]].w-=res;
            e[pr[x]+1].w+=res;
            x=pre[x];
        }
    }
}
int u,v,w,S,T;
signed main(){
    n=read(),m=read();S=read(),T=read();
    for(register int i=1;i<=m;++i){
        u=read(),v=read(),w=read();
        add(u,v,w);add(v,u,0);
    }   
    EK(S,T);
    printf("%lld\n",ans);
    return 0;
}

by Sol1 @ 2020-03-15 15:46:16

@Lates EK本来就能过(


by Lates @ 2020-03-15 15:46:57

@ClCN 复杂度不是O(nm^2)的吗


by Sol1 @ 2020-03-15 15:47:29

@Lates 但是一般不会到那个上界吧(

或者是您常数小 Orz


by StudyingFather @ 2020-03-15 15:48:06

网络流模板仅用来测板子正确性(


by __gcd @ 2020-03-15 15:48:25

@Lates 照你这么算Dinic好像也会炸掉


by Lates @ 2020-03-15 15:49:50

@ClCN @StudyingFather @一只大头 谢谢


by LTb_ @ 2020-03-15 16:11:35

因为你谷数据弱(

可以交到LOJ上看看qwq


by Lates @ 2020-03-15 17:53:43

@LTb_ loj EK+邻接矩阵都过了


|