最大流板子第十个点WA了,在线求调

P3376 【模板】网络最大流

P_VICVIC_R @ 2023-12-29 10:37:12

rt,可能马蜂有那么一点点点清新,轻喷qwq

#include<bits/stdc++.h>
#define f1 first 
#define f2 second
#define int long long
#define V_(T) vector<T>
#define P_(T1,T2) pair<T1,T2>

using namespace std;

static const int ni=2050;
static const int N=1000000;
static const int inf=0x7fffffff;
static const int INF=0x7f7f7f7f7f7f7f;

namespace Graph{
class graph{
public:
    struct Edge{
        int nxt;
        int to;
        int val;
    };
    int tot=1;
    int n_,m_;
    V_(int) sign;
    V_(Edge) e;
    graph(int _n_=0,int _m_=0)
:n_(_n_),m_(_m_)
{
    for(int i=0;i<=(m_<<1);i++){sign.push_back(0);e.push_back({0,0,0});}
} 
    ~graph(){}
    void add(int fro,int to,int val)
{
    tot++;
    e[tot].to=to;
    e[tot].val=val;
    e[tot].nxt=sign[fro];
    sign[fro]=tot;
}
   void add(int fro,int to)
{
    tot++;
    e[tot].to=to;
    e[tot].nxt=sign[fro];
    sign[fro]=tot;
}   
};
static const graph Empty;
class Dinic 
{
private:
    Graph::graph GL;
    V_(int) cvrg;
    V_(int) ncur;
    int S_,T_; 
    #define sign(x) GL.sign[x]
    #define to(x) GL.e[x].to
    #define vl(x) GL.e[x].val
    #define nx(x) GL.e[x].nxt
inline bool bfs()
{
    cvrg=V_(int) (GL.n_+1,0);
    queue<int> ql;
    ql.push(S_);
    cvrg[S_]=1;
    while(!ql.empty()){
        int rt=ql.front();
        ql.pop();
        for(int i=sign(rt);i;i=nx(i)){
            int to=to(i);
            if(!cvrg[to]&&vl(i)){
                cvrg[to]=cvrg[rt]+1;
                ql.push(to);
                if(to==T_){return true;}
            }
        }
    }
    return false;
}
inline int dfs(int rt,int flo)
{
    if(rt==T_){
        return flo;
    }
    int tmp_sum=flo;
    for(int i=ncur[rt];i&&tmp_sum;i=nx(i)){
        ncur[rt]=i;
        int to=to(i);
        if(cvrg[to]==cvrg[rt]+1&&vl(i)){
            int fl=dfs(to,min(flo,vl(i)));
            if(!fl){
                cvrg[to]=0;
            }
            vl(i)-=fl;
            vl(i^1)+=fl;
            tmp_sum-=fl;
        }
    }
    return flo-tmp_sum;
}
    #undef sign
    #undef to
    #undef vl
    #undef nx
public:
    int maxinum_flow;
    Dinic(class Graph::graph G_= Empty,int S=1,int T=1)
:GL(G_),S_(S),T_(T)
{
    maxinum_flow=0;
    while(bfs()){
    // bfs();
        ncur=GL.sign;
        while(int tmp=dfs(S,INF))
        {
            maxinum_flow+=tmp;
        }
    }
}
    ~Dinic(){}
};

}
using namespace Graph; 
int n,m;
int S,T;
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cout.tie(0);
    std::cin.tie(0);
    cin>>n>>m>>S>>T;
    graph G(n+n,m+m);
    for(int i=0;i<m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        G.add(x,y,z);
        G.add(y,x,0);
    }
    Dinic ans(G,S,T);
    cout<<ans.maxinum_flow;
    return 0;
}

by _anll_ @ 2023-12-29 10:38:21

看不懂,但先膜为敬awa


by P_VICVIC_R @ 2023-12-29 10:39:17

额额是用类写的,可能有一点点点怪吧awq


by DeusExMachina @ 2023-12-29 10:59:46

https://www.luogu.com.cn/paste/cc9on0aj

给你格式化了一下代码


by Union_of_Britain @ 2023-12-29 10:59:51


by _qingshu_ @ 2023-12-29 11:06:33

@PAVIC_victor

把第 91 行的

int fl=dfs(to,min(flo,vl(i)));

改成

int fl=dfs(to,min(tmp_sum,vl(i)));

就好了,你流量没有实时减少


by P_VICVIC_R @ 2023-12-29 11:07:46

%%% @qingshu %%%


by _anll_ @ 2023-12-29 11:07:54

!惊现情书哥哥!先膜为敬


by carefree_Zhuang @ 2024-01-29 16:41:25

%%%


|