最大流Dinic算法

Description

在残余网络上bfs标号建立层次图，然后在层次图上多次dfs不断寻找增广路径增广，增广路径上的结点要按层次图上标号递增的顺序。如果找不到增广路径就重新标记层次图，直到元源点与汇点不再相连。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 1e3 + 10;
const int M = 2e3 + 10;

struct Edge
{
int to, c, next;
    Edge() {}
    Edge(int to, int c, int next) : to(to), c(c), next(next) {}
} edge[M];
int adj[N], tot;

void init()
{
    memset(adj, -1, sizeof(adj));
    tot = 0;
}

void add(int u, int v, int c)
{
    edge[tot] = Edge(v, c, adj[u]);
    adj[u] = tot++;
    edge[tot] = Edge(u, 0, adj[v]);
    adj[v] = tot++;
}

int level[N];
queue<int> q;
bool bfs(int s, int t)
{
while (!q.empty()) q.pop();
    memset(level, -1, sizeof(level));
    level[s] = 0; q.push(s);
while (!q.empty())
    {
int u = q.front(); q.pop();
for (int i = adj[u]; i != -1; i = edge[i].next)
        {
            Edge &e = edge[i];
if (e.c && level[e.to] == -1)
            {
                level[e.to] = level[u] + 1;
if (e.to == t) return true;
                q.push(e.to);
            }
        }
    }
return false;
}

int cur[N];
int dfs(int u, int t, int flow)
{
if (u == t) return flow;
for (int &i = cur[u]; i != -1; i = edge[i].next)
    {
        Edge &e = edge[i];
if (e.c && level[e.to] > level[u])
        {
int f = dfs(e.to, t, min(flow, e.c));
if (f)
            {
                e.c -= f;
                edge[i ^ 1].c += f;
return f;
            }
        }
    }
return 0;
}

int dinic(int s, int t)
{
int flow = 0;
while (bfs(s, t))
    {
        memcpy(cur, adj, sizeof(adj));
int f; int c = 0;
while (f = dfs(s, t, INF)) flow += f;
    }
return flow;
}

int main()
{
int n, m;
    scanf("%d%d", &n, &m);
    init();
while (m--)
    {
int u, v, c;
        scanf("%d%d%d", &u, &v, &c);
        add(u, v, c);
    }
int s, t;
    scanf("%d%d", &s, &t);
int ans = dinic(s, t);
    printf("%d\n", ans);
return 0;
}

Input

第一行给出结点数\(n\)和边数\(m\)，接下来的\(m\)行，每行给出两个三个整数\(u\)，\(v\)和\(c\)，表示从\(u\)到\(v\)有一条容量为\(c\)的边。最后一行给出源点\(s\)和汇点\(t\)。

Output

输出一个整数，表示最大流。

Sample Input

秒客网