萌新求助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:28:23

@幻离ian EK 这道题会被卡吧
而且显然你用邻接矩阵存图跑一遍 dfs 就差不多 n 方肯定过不了了啊


by 幻离ian @ 2021-07-08 17:34:09

旁边的人用EK过了


by Rolling_L @ 2021-07-08 17:35:19

@SIXIANG

这题n不是200吗,n方应该能过吧


by 幻离ian @ 2021-07-08 17:35:21

@SIXIANG

代码基本相似

https://www.luogu.com.cn/record/52609961


by SIXIANG32 @ 2021-07-08 17:39:28

@ytl_jr 要跑多变 bfs 嗷嗷嗷嗷嗷啊


by SIXIANG32 @ 2021-07-08 17:40:14

@幻离ian 我记得我看过有人用 EK 做的,用 vector 存图,然后用邻接矩阵存边权,记得判重边
我记得好像是这样的,如果说错了勿喷


by Rolling_L @ 2021-07-08 17:42:25

@SIXIANG

多遍bfs时间大约为O(nm^2),常数小的话应该能过。而且那份AC代码是我写的


by SIXIANG32 @ 2021-07-08 17:44:28

@ytl_jr 哦
不是 lz 的 bfs 是 n ^ 2 的啊
但我的意思真的不是这个算法是 n ^ 2 的啊啊啊啊啊
还有好好写 Dinic 不香吗,我记得草地排水就可以用 EK 过,为啥不写那题啊(


by 幻离ian @ 2021-07-08 17:47:33

@SIXIANG

我也用星向图写了一遍,也卡这两个点,而且查出来是卡while了

https://www.luogu.com.cn/record/52610405


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

@幻离ian 不是他可能有重边啊啊啊啊啊
听说判了重边以后就行了
具体怎么搞我记得有一篇题解有些,但我写的是 Dinic(


| 下一页