最大流 dinic算法

洛谷 P3376

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
#include <queue>
#include <numeric>
#include <functional>
#include <set>
#include <cmath>
#include <random>
#include <chrono>
#include <iomanip>

//#define NDEBUG
//#include <cassert>

#define DEBUG(x) cout<<(x)<<endl;
#define DEBUGA(l,r,a) for (int i=l;i<=r;++i) cout<<a[i]<<' ';cout<<endl;
#define lson (rt<<1)
#define rson (rt<<1|1)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const int maxn=2e5+7;
const int inf=(1u<<31)-1;
const int mod=998244353;
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());

inline int read(){
    int x=0,w=0;char ch=0;
    while (ch<'0'||ch>'9') {w|=ch=='-';ch=getchar();}
    while (ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return w?-x:x;
}

inline void write(int x){
    if (x<0) putchar('-'),x=-x;
    if (x>9) write(x/10);
    putchar(x%10+'0');
}

struct MF{
    //dinic

    struct edge{
        int v, nxt, cap, flow;
        edge(){}
        edge(int v, int nxt, int cap, int flow): v(v), nxt(nxt), cap(cap), flow(flow) {}
    };
    vector<edge> e;
    int cnt;
    vector<int> head, cur;

    int n, m, S, T;
    ll maxflow;
    vector<int> dep;

    MF(int _n,int _m,int _S,int _T): n(_n), m(_m), S(_S), T(_T){
        head.assign(n+1, -1);
        cnt=maxflow=0;
        e.assign(m<<1, edge());
    }

    void addedge(int u, int v, int w){
        e[cnt] = {v, head[u], w, 0};
        head[u] = cnt++;
        e[cnt] = {u, head[v], 0, 0};
        head[v] = cnt++;
    }

    bool bfs(){
        queue<int> q;
        dep.assign(n+1, 0);
        dep[S] = 1;
        q.push(S);
        while (!q.empty()){
            int u = q.front(); q.pop();
            for (int i = head[u]; ~i; i = e[i].nxt){
                int v = e[i].v;
                if (!dep[v] && e[i].cap>e[i].flow){
                    dep[v] = dep[u]+1;
                    q.push(v);
                }
            }
        }
        return dep[T];
    }

    int dfs(int u, int flow){
        if (u==T || !flow) return flow;
        int res = 0;
        for (int& i = cur[u]; ~i; i = e[i].nxt){
            int v = e[i].v;
            int d;
            if (dep[v]==dep[u]+1 && (d=dfs(v, min(flow-res, e[i].cap-e[i].flow)))){
                res += d;
                e[i].flow += d;
                e[i^1].flow -= d;
                if (res==flow) return res;
            }
        }
        return res;
    }


    void dinic(){
        while (bfs()){
            cur.assign(head.begin(), head.end());
            maxflow += dfs(S, inf);
        }
    }
};

void solve(){
    int n,m,S,T;
    cin>>n>>m>>S>>T;
    MF mf(n,m,S,T);
    for (int i=1;i<=m;++i){
        int u,v,w;
        cin>>u>>v>>w;
        mf.addedge(u,v,w);
    }
    mf.dinic();
    cout<<mf.maxflow<<endl;
}


int main(int argc,char* argv[]){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T=1;
//    cin>>T;
    while (T--) solve();

    return 0;
}