萌新求助EK,T了两个点

P3376 【模板】网络最大流

幻离ian @ 2021-07-08 17:23:51

#include <iostream>
#include <queue>
#include <cstring>
#include <cmath>
#define int long long
using namespace std;
int INF=1ll<<62;
int n,m,s,t,res,tot,pre[205],vis[205],u,v,c;
int f[205][205];
inline int bfs(){
    memset(vis,0,sizeof(vis));
    pre[t]=0;
    queue<int>q;
    q.push(s);
    vis[s]=1;
    int lf=INF;
    while(!q.empty()){
        int x = q.front();q.pop();
        if(x==t)break;
        for(int i = 1;i<=n;i++){
            if(vis[i]==0&&f[x][i]>0){
                q.push(i);
                lf=min(lf,f[x][i]);
                pre[i]=x;
                vis[i]=1;
            }
        }
    }
    if(pre[t]==0)return 0;
    return lf; 
}
inline void upt(int flow){
    int x=t;
    while(x!=s){
        f[pre[x]][x]-=flow;
        f[x][pre[x]]+=flow;
        x=pre[x];
    }
}
signed main(){
    cin>>n>>m>>s>>t;
    for(int i = 1;i<=m;i++){
        cin>>u>>v>>c;
        f[u][v]+=c;
    }
    while(1){
        res=bfs();
        if(res==0)break;
        upt(res);
        tot+=res;
    }
    cout<<tot;
    return 0;
}

by SIXIANG32 @ 2021-07-08 17:48:58

EK 复杂度假的啊兄弟们
Dinic 才是王道啊兄弟们


by YamadaRyou @ 2021-07-08 19:37:03

@SIXIANG ?EK复杂度是 O(nm^2) 没毛病啊


by SIXIANG32 @ 2021-07-09 08:00:55

@WA王子 我说这道题 EK 过不了啊啊啊啊啊


by YamadaRyou @ 2021-07-09 10:35:00

@SIXIANG az


by Coros_Trusds @ 2021-07-26 17:45:37

@幻离ian

这道题要想笑着AC就必须写 Dinic+弧优化


上一页 |