最大流模板题

我用的模板是Kuangbin大神写的,此模板还可处理带费用问题。

Kuangbin模板获取

请注意该dinic模板 点下标 从0开始。

#include<bits/stdc++.h>
using namespace std;
#define de_x(x) cout<<"debug_val: "<<x<<endl;
#define de_ve(x) for(auto it: x) cout<<it<<" ";
#define rep(i,a,n) for (int i=a;i<n;i++)
#define _rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
const ll MOD = 1e9 + 7;
ll ksm(ll a, ll b) { ll res = 1; a %= MOD; assert(b >= 0); for (; b; b >>= 1) { if (b & 1)res = res * a % MOD; a = a * a % MOD; }return res; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
int _;
/**********

*************/

const int MAXN = 2010;//点数的最大值
const int MAXM = 1200010;//边数的最大值
const int INF = 0x3f3f3f3f;
#define int long long
struct Edge {
    int to, next, cap, flow;
}edge[MAXM];//注意是 MAXM
int tol;
int head[MAXN];
void init() {
    tol = 2;
    memset(head, -1, sizeof(head));
}
void addedge(int u, int v, int w, int rw = 0) {
    edge[tol].to = v;
    edge[tol].cap = w;
    edge[tol].flow = 0;
    edge[tol].next = head[u];
    head[u] = tol++;

    edge[tol].to = u;
    edge[tol].cap = rw;
    edge[tol].flow = 0;
    edge[tol].next = head[v];
    head[v] = tol++;
}
int Q[MAXN];
int dep[MAXN], cur[MAXN], sta[MAXN];
bool bfs(int s, int t, int n) {
    int front = 0, tail = 0;
    memset(dep, -1, sizeof(dep[0]) * (n + 1));
    dep[s] = 0;
    Q[tail++] = s;
    while (front < tail) {
        int u = Q[front++];
        for (int i = head[u]; i != -1; i = edge[i].next) {
            int v = edge[i].to;
            if (edge[i].cap > edge[i].flow && dep[v] == -1) {
                dep[v] = dep[u] + 1;
                if (v == t)return true;
                Q[tail++] = v;
            }
        }
    }
    return false;
}
int dinic(int s, int t, int n) {
    int maxflow = 0;
    while (bfs(s, t, n)) {
        for (int i = 0; i < n; i++) cur[i] = head[i]; 
        int u = s, tail = 0;
        while (cur[s] != -1) {
            if (u == t) {
                int tp = INF;
                for (int i = tail - 1; i >= 0; i--)
                    tp = min(tp, edge[sta[i]].cap - edge[sta[i]].flow);
                maxflow += tp;
                for (int i = tail - 1; i >= 0; i--) {
                    edge[sta[i]].flow += tp;
                    edge[sta[i] ^ 1].flow -= tp;
                    if (edge[sta[i]].cap - edge[sta[i]].flow == 0)
                        tail = i;
                }
                u = edge[sta[tail] ^ 1].to;
            }
            else if (cur[u] != -1 && edge[cur[u]].cap > edge[cur[u
            ]].flow && dep[u] + 1 == dep[edge[cur[u]].to]) {
                sta[tail++] = cur[u];
                u = edge[cur[u]].to;
            }
            else {
                while (u != s && cur[u] == -1)
                    u = edge[sta[--tail] ^ 1].to;
                cur[u] = edge[cur[u]].next;
            }
        }
    }
    return maxflow;
}
signed main()
{
    int n, m;
    cin >> n >> m ;
    init();
    for (int i = 0; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        addedge(u-1, v-1, w);
    }

    cout << dinic(0, m-1, m);

    return 0;
}