dinic板子

本文主要是介绍dinic板子，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

loj上偷学长的（

#include <cstdio>
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(int x = 0, char ch = getchar()) {
    while (!isdigit(ch))
        ch = getchar();

    while (isdigit(ch))
        x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();

    return x;
}

const int N = 1e2 + 7, M = 1e4 + 7;
const ll inf = 1e18;

int n, m, S, T;
ll ans, c[M];
int head[N], to[M], nx[M], id = 1;
inline void add(int a, int b, int cc) {
    nx[++id] = head[a];
    head[a] = id;
    to[id] = b;
    c[id] = cc;
}
inline void Add(int a, int b, int c) {
    add(a, b, c);
    add(b, a, 0);
}

int q[N], hd, tl;
int dis[N], Hd[N];

inline bool bfs() {
    memset(dis, 0x3f, sizeof(dis));
    memcpy(head, Hd, sizeof(head));
    q[hd = tl = 1] = S;
    dis[S] = 0;

    while (hd <= tl) {
        int x = q[hd++];

        for (int i = head[x]; i; i = nx[i])
            if (c[i]) {
                int t = to[i];

                if (dis[t] > dis[x] + 1) {
                    dis[t] = dis[x] + 1;
                    q[++tl] = t;
                }
            }

        if (x == T)
            return 1;
    }

    return 0;
}

ll dfs(int x, ll in) {
    if (x == T)
        return in;

    ll rest = in, go;

    for (int i = head[x]; i; head[x] = i = nx[i])
        if (c[i]) {
            int t = to[i];

            if (dis[t] == dis[x] + 1) {
                go = dfs(t, min(rest, c[i]));

                if (go)
                    c[i] -= go, c[i ^ 1] += go, rest -= go;
                else
                    dis[t] = 0;
            }

            if (!rest)
                break;
        }

    return in - rest;
}

int main() {
    n = read();
    m = read();
    S = read();
    T = read();

    while (m--) {
        int u = read(), v = read();
        Add(u, v, read());
    }

    memcpy(Hd, head, sizeof(Hd));

    while (bfs())
        ans += dfs(S, inf);

    printf("%lld\n", ans);
    return 0;
}

这篇关于dinic板子的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！