网络流学习

https://www.cnblogs.com/SYCstudio/p/7260613.html

https://cn.vjudge.net/contest/282008#discuss

https://www.cnblogs.com/LUO77/p/6115057.html

Dinic(裸的最大流)

#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

typedef long long LL;
typedef double DB;
typedef pair <int, int> PII;
const int MAXN = 1e4 + 10, MAXM = 1e5 + 10;
const LL INF = 1e15;

inline LL in()
{
    LL x = 0, flag = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') flag = -1; ch = getchar(); }
    while (ch >='0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    return x * flag;
}

int n, m, s, t;

struct Adj
{
    int nex, to;
    LL w;
} adj[MAXM << 1];
int head[MAXN], nume, cur[MAXN];
void addedge(int from, int to, LL w)
{
    adj[++nume] = (Adj) { head[from], to, w };
    head[from] = nume;
}

int lev[MAXN];
queue <int> Q;
bool BFS(int s, int t)
{
    while (!Q.empty()) Q.pop();
    memset(lev, 0, sizeof lev);
    lev[s] = 1;
    Q.push(s);
    while (!Q.empty())
    {
        int u = Q.front(); Q.pop();
        for (int i = head[u]; i != -1; i = adj[i].nex)
        {
            int v = adj[i].to;
            if (!lev[v] && adj[i].w > 0)
            {
                lev[v] = lev[u] + 1;
                Q.push(v);
            }
        }
    }
    return lev[t] != 0;
}
LL DFS(int u, int t, LL flow)
{
    if (u == t) return flow;
    LL sum = 0;
    for (int &i = cur[u]; i != -1; i = adj[i].nex)
    {
        int v = adj[i].to;
        if (lev[v] == lev[u] + 1 && adj[i].w)
        {
            LL f = DFS(v, t, min(flow, adj[i].w));
            adj[i].w -= f;
            adj[i ^ 1].w += f;
            sum += f;
            flow -= f;
            if (flow == 0) break;
        }
    }
    return sum;
}
LL Dinic()
{
    LL ret = 0;
    while ( BFS(s, t) )
    {
        copy(head, head + n + 1, cur);
        ret += DFS(s, t, INF);
    }
    return ret;
}

int main()
{
    nume = -1;
    memset(head, -1, sizeof head);
    n = in(), m = in(); s = in(), t = in();
    for (int i = 1; i <= m; i ++)
    {
        int u = in(), v = in();
        LL w = in();
        addedge(u, v, w);
        addedge(v, u, 0);
    }
    printf("%lld\n", Dinic());
    return 0;
}

https://blog.csdn.net/clove_unique/article/details/54884437

上下界网络流

无源汇可行流

有源汇可行流

有源汇最大流

有源汇最小流

网络流学习笔记

原文：https://www.cnblogs.com/Kuonji/p/11844106.html