AcWing算法进阶课-1.9.1Dinic/ISAP求最小割

发布时间:2023年12月20日

算法进阶课整理

CSDN个人主页:更好的阅读体验

Start

原题链接
题目描述

给定一个包含 n n n 个点 m m m 条边的有向图,并给定每条边的容量,边的容量非负。

图中可能存在重边和自环。求从点 S S S 到点 T T T 的最小割。

输入格式

第一行包含四个整数 n , m , S , T n,m,S,T n,m,S,T

接下来 m m m 行,每行三个整数 u , v , c u,v,c u,v,c,表示从点 u u u 到点 v v v 存在一条有向边,容量为 c c c

点的编号从 1 1 1 n n n

输出格式

输出点 S S S 到点 T T T 的最小割。

如果从点 S S S 无法到达点 T T T 则输出 0 0 0

数据范围

2 ≤ n ≤ 10000 2 \le n \le 10000 2n10000,
1 ≤ m ≤ 100000 1 \le m \le 100000 1m100000,
0 ≤ c ≤ 10000 0 \le c \le 10000 0c10000,
S ≠ T S \neq T S=T


思路

最大流最小割定理

对于任意一个流网络 G = ( V , E ) G=(V,E) G=(V,E) 都满足:

  1. 可行流 f f f 是最大流。

? \Leftrightarrow ?

  1. 可行流 f f f 的残量网络中不存在增广路。

? \Leftrightarrow ?

  1. ? [ S , T ] , ∣ f ∣ = c ( S , T ) \exist [\text S,\text T],|f|=c(\text S,\text T) ?[S,T],f=c(S,T)

证明

  • 1 ? 2 1\Rightarrow 2 1?2:反证法。假设 f f f 是最大流,且 G f G_f Gf? 存在增广路径。这说明 G f G_f Gf? 存在至少一个流量大于 0 0 0 的可行流 f ′ f' f。这样能构造出原网络中另一个可行流 f + f ′ f+f' f+f,且 ∣ f + f ′ ∣ > ∣ f ∣ |f+f'|>|f| f+f>f,说明 f f f 不是最大流,与假设矛盾。
  • 2 ? 3 2\Rightarrow 3 2?3:构造一个割,使得它在残量网络中不存在增广路径,且 ∣ f ∣ = c ( S , T ) |f|=c(\text S,\text T) f=c(S,T)。定义集合 S \text S S 为在 G f G_f Gf? 中从 S S S 出发,沿容量大于 0 0 0 的边走能走到的所有的点。由于残量网络中不存在增广路径,所以集合 S \text S S 中不可能包含 T T T。在定义集合 T = V ? S \text T = \text V - \text S T=V?S,即为构造的合法割。对于正向边 ( u , v ) [ u ∈ S , v ∈ T ] (u,v)[u\in \text S,v\in \text T] (u,v)[uS,vT],由于 u , v u,v u,v 不相通,所以 f ′ ( u , v ) = 0 f'(u, v)=0 f(u,v)=0,所以 f ( u , v ) = c ( u , v ) f(u,v)=c(u,v) f(u,v)=c(u,v)。对于反向边 ( u , v ) [ u ∈ T , v ∈ S ] (u,v)[u\in \text T,v\in \text S] (u,v)[uT,vS] 同理, c ′ ( v , u ) = 0 c'(v,u)=0 c(v,u)=0,即 f ( u , v ) = 0 f(u,v)=0 f(u,v)=0。发现原网络中 ? ( u , v ) ( u ∈ S , v ∈ T ) \forall (u,v)(u\in\text S,v\in\text T) ?(u,v)(uS,vT),都有 f ( u , v ) = c ( u , v ) , f ( v , u ) = 0 f(u,v)=c(u,v),f(v,u)=0 f(u,v)=c(u,v),f(v,u)=0。因此 ∣ f ∣ = f ( S , T ) = ∑ u ∈ S ∑ v ∈ T f ( u , v ) ? ∑ u ∈ S ∑ v ∈ T f ( v , u ) = ∑ u ∈ S ∑ v ∈ T f ( u , v ) = ∑ u ∈ S ∑ v ∈ T c ( u , v ) = c ( S , T ) |f|=f(\text S,\text T)=\sum_{u\in\text S}\sum_{v\in\text T}f(u,v)-\sum_{u\in\text S}\sum_{v\in\text T}f(v,u)=\sum_{u\in\text S}\sum_{v\in\text T}f(u,v)=\sum_{u\in\text S}\sum_{v\in\text T}c(u,v)=c(\text S,\text T) f=f(S,T)=uS?vT?f(u,v)?uS?vT?f(v,u)=uS?vT?f(u,v)=uS?vT?c(u,v)=c(S,T)
  • 3 ? 1 3\Rightarrow 1 3?1:由 本文 最小割的推论中已知 ∣ f ∣ ≤ c ( S , T ) |f|≤c(\text S,\text T) fc(S,T),且最大流是可行流的一种,所以最大流 ≤ c ( S , T ) \leq c(\text S,\text T) c(S,T)。易知 ∣ f ∣ ≤ |f|\leq f 最大流,而 ∣ f ∣ = c ( S , T ) ≥ |f|=c(\text S,\text T)\geq f=c(S,T) 最大流。即 ∣ f ∣ ≥ |f|\geq f 最大流。综上得出 ∣ f ∣ = |f|= f= 最大流。已证最大流 ≤ \leq 最小割,而最小割又是割的容量的最小值,得出最小割 ≤ c ( S , T ) = ∣ f ∣ ≤ \leq c(\text S,\text T)=|f|\leq c(S,T)=f 最大流,即最小割 ≤ \leq 最大流,最终得出最大流 = 最小割。

因此要求最小割,只需求原图的最大流即可。


Dinic 算法其实是 EK 算法的一个暴力的优化,EK 算法每次只能搜索一条增广路径,而 Dinic 算法每次都用 DFS 的形式尽可能多的搜索增广路径。

而图中可能存在环,为了保证 DFS 的过程中不会造成死循环,这里可以使用分层图,这样每次都是一层一层往下搜索,就不会出现死循环。

  1. BFS 建立分层图
  2. DFS 找出所有能增广的路径
  3. 累加最大流量

注意: Dinic 算法对于优化非常敏感,如果优化的不好就可能直接 TLE

算法时间复杂度 O ( n 2 m ) O(n^2m) O(n2m)
AC Code

C + + \text{C}++ C++

#include <iostream>
#include <cstring>

using namespace std;

const int N = 10010, M = 200010;
const int INF = 1e9;

int n, m, S, T;
int h[N], e[M], ne[M], f[M], idx;
int d[N], q[N], cur[N];
// d[] 存分层图中每个点的深度
// q[] 手写队列
// cur[] 当前弧优化

inline void add(int a, int b, int c)
{
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++ ; // 正向边
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++ ; // 反向边,用于反悔
}

bool bfs()
{
    memset(d, -1, sizeof d); // 记得初始化
    int hh = 0, tt = 0;
    q[0] = S, d[S] = 0, cur[S] = h[S];
    // 将源点加入队列,源点深度为0,初始化源点当前弧为表头

    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (d[j] == -1 && f[i]) // 存在增广路才能从这里分层
            {
                d[j] = d[t] + 1; // 更新深度
                cur[j] = h[j]; // 所有点当前弧最开始都是表头
                if (j == T) return true; // 如果找到汇点了就说明有增广路
                q[ ++ tt] = j;
            }
        }
    }
    return false; // 没有增广路
}

int find(int u, int lim) // DFS,u是当前点,lim是u之前的路径能流过的最大值
{
    if (u == T) return lim; // 如果已经流到汇点了就返回这个最大值
    int flow = 0; // 当前往下流的流量
    for (int i = cur[u]; ~i && flow < lim; cur[u] = i, i = ne[i])
    // 注意应从当前弧开始遍历,并且每次要更新。没有剩余流量也应该退出
    {
        int j = e[i];
        if (d[j] == d[u] + 1 && f[i])
        // 按分层图遍历,防止死循环
        {
            int t = find(j, min(f[i], lim - flow));
            // 找到后面能流的最大值
            if (!t) d[j] = -1;
            // 如果没有流量那么说明后面没有增广路了,这个点不会用到,将深度设为-1
            f[i] -= t, f[i ^ 1] += t, flow += t;
            // 当前边减流量,反向边加流量,实际流量加流量
        }
    }
    return flow;
}

int dinic()
{
    int r = 0, flow = 0;
    while (bfs()) while ((flow = find(S, INF))) r += flow;
    // 只要存在增广路就一直DFS,直到DFS出的流量为0
    return r;
}

int main()
{
    int a, b, c;
    memset(h, -1, sizeof h);

    scanf("%d%d%d%d", &n, &m, &S, &T);
    while (m -- )
    {
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    printf("%d\n", dinic());
    return 0;
}

228aa7bed3e021faf24cf8560d3e47bb.gif

最后,如果觉得对您有帮助的话,点个赞再走吧!

文章来源:https://blog.csdn.net/xingchen_2008/article/details/135116494
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。