网络最大流和Dinic算法

在有向流量网络上求从源点到汇点的最大可能流量的问题，称为网络流问题。
流量网络中一些边的流量已被部分占用时，称其为残量网络。
在残量网络中一条从源点到汇点的有有效流量的路径称为增广路。

对于网络中的每一条边，构造一条与其方向相反，流量为零的边。在减少正向边可用流量的同时，增加反向边的可用流量。

Dinic算法寻找增广路时分为以下两步：
1. 通过广度优先搜索，以源点为起始点，将残量网络分层。

queue<int> Q;
bool bfs() {                          // 没什么重点的广搜分层
    for (int i = 1; i <= n; i++)
        dis[i] = infinity;
    Q.push(s);
    dis[s] = 0;
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        for (node* p = h[u]; p != nullptr; p = p->next) {
            int v = p->v, flow = p->flow;
            if (flow > 0)             // 只考虑有残余流量的边
                if (dis[v] == infinity) {
                    dis[v] = dis[u] + 1;
                    Q.push(v);
                }
        }
    }
    if (dis[t] == infinity)
        return false;
    else
        return true;
}

2. 在残量网络中以深度优先搜索的方式寻找可用的增广路。在分层网络中，要求搜索下一步的节点在下一层之中。
在寻找增广路时，不止找一条增广路，而是在当前节点流量限制没有用完时不断对于每一个可行节点扩展流量，形成的实际是多条增广路。

int dfs(int u, int limit) {
    if (u == t || limit == 0)                         // 如果到达了汇点直接返回当前流量限制作为有效流量
        return limit;                                 // 如果流量限制为零直接返回零
    int val = 0;                                      // ↓当流量限制没有用完时继续扩展
    for (node* p = h[u]; p != nullptr && limit > 0; p = p->next) {
        int v = p->v, f;
        int& flow = p->flow;
        if (dis[v] == dis[u] + 1 &&                   // 如果下一个节点在下一层并且
            (f = dfs(v, min(limit, flow))) != 0) {    // 搜索这个节点后所得到的有效流量不为零
            flow -= f;                              // 当前边的残余流量减少
            p->rev->flow += f;                      // 反向边的残余流量增加
            limit -= f;                             // 流量限制减少
            val += f;                               // 有效流量增加
        }
    }
    return val;                                       // 返回有效流量
}

以下为Dinic算法的主体：

int dinic() {
    int ans = 0;
    while (bfs())
        ans += dfs(s, infinity);
    return ans;
}

当前弧优化：一次dfs可能会多次经过一个节点，在第二次经过一个节点时，第一次经过时出边表中前几项边已经没有剩余可用的流量，以后经过同一个节点时不用再次递归。我们开一个数组记录每一个节点下一次应该从哪一条边开始继续递归。

// BFS过程没有变化

node* cur[MaxN];

int dfs(int u, int limit) {
    if (u == t || limit == 0)
        return limit;
    int val = 0;  // ↓注意引用符号&，在改变p的值时cur[u]也会跟着改变
    for (node*& p = cur[u]; p != nullptr; p = p->next) {
        int v = p->v, f;
        int& flow = p->flow;
        if (dis[v] == dis[u] + 1 &&
            (f = dfs(v, min(limit, flow))) != 0) {
            flow -= f;
            p->rev->flow += f;
            limit -= f;
            val += f;
        }
        if (limit <= 0)
            break; // 在转向下一条边前跳出，防止限制流量用完而递归流量未用完时跳过而降低效率（没什么关系啦）
    }
    return val;
}

int dinic() {
    int ans = 0;
    while (bfs()) {
        for (int i = 1; i <= n; i++)
            cur[i] = h[i];   // 每次找增广路开始时先从第一条边开始递归
        ans += dfs(s, infinity);
    }
    return ans;
}

时间复杂度：广搜\(O(n)\)，深搜\(O(nm)\)，总体\(O(n^2 m)\)
在二分图中：广搜\(O(1)\)，深搜\(O(\sqrt{n})\)，总体\(O(\sqrt{n}m)\)

以下是版子

constexpr int infinity = 1e8;
constexpr int MaxN = 10000 + 10, MaxM = 100000 + 10;

int n, m;
int s, t;

struct node {
    int v, flow;
    node* next;
    node* rev;
};

node* h[MaxN];
node mem[2 * MaxM], *memtop = mem;
#define ALLOCATE (++memtop)

void addedge(int u, int v, int flow) {
    node* p1 = ALLOCATE;
    p1->v = v;
    p1->flow = flow;
    p1->next = h[u];
    h[u] = p1;
    node* p2 = ALLOCATE;
    p2->v = u;
    p2->flow = 0;
    p2->next = h[v];
    h[v] = p2;
    p1->rev = p2;
    p2->rev = p1;
}

int dis[MaxN];

queue<int> Q;
bool bfs() {
    for (int i = 1; i <= n; i++)
        dis[i] = infinity;
    Q.push(s);
    dis[s] = 0;
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        for (node* p = h[u]; p != nullptr; p = p->next) {
            int v = p->v, flow = p->flow;
            if (flow > 0)
                if (dis[v] == infinity) {
                    dis[v] = dis[u] + 1;
                    Q.push(v);
                }
        }
    }
    if (dis[t] == infinity)
        return false;
    else
        return true;
}

int dfs(int u, int limit) {
    if (u == t || limit == 0)
        return limit;
    int val = 0;
    for (node* p = h[u]; p != nullptr&&limit > 0; p = p->next) {
        int v = p->v, f;
        int& flow = p->flow;
        if (dis[v] == dis[u] + 1 && (f = dfs(v, min(limit, flow))) != 0) {
            flow -= f;
            p->rev->flow += f;
            limit -= f;
            val += f;
        }
    }
    return val;
}

int dinic() {
    int ans = 0;
    while (bfs())
        ans += dfs(s, infinity);
    return ans;
}