萌新求助37分 7RE

P3376 【模板】网络最大流

sam_hengxuan @ 2022-07-18 10:03:41

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define LL long long
#define mem(x,y) memset(x,y,sizeof(x))

using namespace std;

const int MAXN = 205;
const int MAXM = 5005;
int n, m, s, t, tot = 1;
int lv[MAXN * 2], cur[MAXN * 3];
struct node {
    int u, v, next;
    LL w;
}E[MAXM * 3];
int first[MAXM * 3];

void add(int u, int v, LL w) {
    E[++tot].u = u;
    E[tot].v = v;
    E[tot].w = w;
    E[tot].next = first[u];
    first[u] = tot;
}

bool bfs() {
    memset(lv, -1, sizeof(lv));
    lv[s] = 0;
    for(int i = 1; i <= tot; i++) cur[i] = first[i];
    queue<int> q;
    q.push(s);
    while(!q.empty()) {
        int p = q.front();
        q.pop(); 
        //cout << p << endl;
        for(int i = first[p]; i != -1; i = E[i].next) {
            int to = E[i].v;
            LL vol = E[i].w;
            //cout << "->" << to << " " << vol << endl;
            if(vol > 0 && lv[to] == -1)
                lv[to] = lv[p] + 1, q.push(to);
        }
    }
    return lv[t] != -1;
}

LL dfs(int p = s, LL flow = INF) {
    if(p == t) return flow;
    LL rmn = flow;
    for(int i = cur[p]; i != -1 && rmn != 0; i = E[i].next) {
        cur[p] = i;
        int to = E[i].v;
        LL vol = E[i].w;
        if(vol > 0 && lv[to] == lv[p] + 1) {
            LL c = dfs(to, min(vol, rmn));
            rmn -= c;
            E[i].w -= c;
            E[i ^ 1].w += c;
        }
    }
    return flow - rmn;
}

LL dinic() {
    LL ans = 0;
    while(bfs()) {
        ans += dfs();
    }
    return ans;
}

int main() {
    memset(first, -1, sizeof(first));
    cin >> n >> m >> s >> t;
    for(int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
        add(v, u, 0);
    }
    //for(int i = first[4]; i != -1; i = E[i].next) cout << E[i].v << endl;
    cout << dinic() << endl;
    return 0;
}

by mzyc_yang2021 @ 2022-07-18 10:19:13

第一次见 萌新 切网络流


|