最大流模板 洛谷P3376 【模板】网络最大流

Edmonds-Karp增广路算法

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

typedef long long ll;

const int N = 205, M = 10005;
const ll INF = 1e12;

int head[N], nxt[M], ver[M]; 
ll edge[M], incf[N];
int vis[N][N], pre[N], v[N];

int tot;
void add_edge(int x, int y, int z)
{
    nxt[++tot] = head[x], ver[tot] = y, edge[tot] = z, head[x] = tot;
    nxt[++tot] = head[y], ver[tot] = x, edge[tot] = 0, head[y] = tot;
}

int s, t;
ll maxflow;

bool bfs()
{
    memset(v, 0, sizeof v);
    queue<int> q;

    q.push(s), v[s] = 1;
    incf[s] = INF;
    while (q.size())
    {
        int x = q.front();
        q.pop();
        for (int i = head[x]; i; i = nxt[i])
        {
            int y = ver[i];
            ll z = edge[i];
            if (v[y] || z == 0) continue;
            incf[y] = min(incf[x], z);
            pre[y] = i;
            if (y == t) return true;
            q.push(y), v[y] = 1;
        }
    }

    return false;
}

void update()
{
    int x = t;
    while (x != s)
    {
        int i = pre[x];
        edge[i] -= incf[t];
        edge[i ^ 1] += incf[t];
        x = ver[i ^ 1];
    }
    maxflow += incf[t];
}

int main()
{
    int n, m;
    scanf("%d%d%d%d", &n, &m, &s, &t);

    tot = 1;
    while (m--)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        if (!vis[x][y]) add_edge(x, y, z), vis[x][y] = tot - 1;//记录x -> y的边的编号
        else edge[vis[x][y]] += z;//处理重边
    }

    maxflow = 0;
    while (bfs()) update();
    printf("%lld", maxflow);

    return 0;
}

Dinic算法
借助分层图，一次寻找多条增广路

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

typedef long long ll;

const int N = 205, M = 10005;
const ll INF = 1e12;

int head[N], now[N], nxt[M], ver[M];
int d[N], vis[N][N];
ll edge[M], w[N][N];

int tot;
void add_edge(int x, int y, int z)
{
    nxt[++tot] = head[x], ver[tot] = y, edge[tot] = z, head[x] = tot;
    nxt[++tot] = head[y], ver[tot] = x, edge[tot] = 0, head[y] = tot;
}

int s, t;

bool bfs()
{
    memset(d, 0, sizeof d);
    queue<int> q;

    q.push(s), d[s] = 1;
    now[s] = head[s];//注意每次now要重新赋值为head
    while (q.size())
    {
        int x = q.front();
        q.pop();
        for (int i = head[x]; i; i = nxt[i])
        {
            int y = ver[i];
            if (d[y] || edge[i] == 0) continue;
            now[y] = head[y];
            d[y] = d[x] + 1;
            if (y == t) return true;
            q.push(y);
        }
    }

    return false;
}

ll dinic(int x, ll flow)
{
    if (x == t) return flow;
    ll ans = 0;
    for (int i = now[x]; i && flow; i = nxt[i])
    {
        now[x] = i;//当前弧优化，已经用过的边都废了
        int y = ver[i];
        if (!edge[i] || d[y] != d[x] + 1) continue;
        ll t = dinic(y, min(flow, edge[i]));
        if (t == 0) d[y] = 0;//这个点不行了，优化掉
        edge[i] -= t;
        edge[i ^ 1] += t;
        flow -= t;
        ans += t;
    }
    return ans;
}

int main()
{
    int n, m;
    scanf("%d%d%d%d", &n, &m, &s, &t);

    tot = 1;
    while (m--)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        if (!vis[x][y]) add_edge(x, y, z), vis[x][y] = tot - 1;
        else edge[vis[x][y]] += z;
    }

    ll maxflow = 0, flow;
    while (bfs())
        while (flow = dinic(s, INF))
            maxflow += flow;
    printf("%lld", maxflow);

    return 0;
}