AcWing算法进阶课-1.1.1EK求最大流

发布时间:2023年12月20日

算法进阶课整理

原题链接
题目描述

给定一个包含 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 ≤ 1000 2 \le n \le 1000 2n1000,
1 ≤ m ≤ 10000 1 \le m \le 10000 1m10000,
0 ≤ c ≤ 10000 0 \le c \le 10000 0c10000,
S ≠ T S \neq T S=T


算法步骤

不断 BFS,用 while 循环不断找残量网络中的增广路径。

每次

  1. 找到增广路径
  2. 更新残量网络
  3. 累加最大流量

跳出循环即得出最大流。

算法时间复杂度 O ( n m 2 ) O(nm^2) O(nm2)

AC Code

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

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010, M = 20010;
const int INF = 1e9;

int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], pre[N];
bool st[N];

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(st, false, sizeof st);
    int hh = 0, tt = 0;
    q[0] = S, d[S] = INF, st[S] = true;
    
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (!st[j] && f[i])
            {
                st[j] = true;
                d[j] = min(d[t], f[i]);
                pre[j] = i;
                if (j == T) return true;
                q[ ++ tt] = j;
            }
        }
    }
    return false;
}

int EK()
{
    int flow = 0;
    while (bfs())
    {
        flow += d[T];
        for (int i = T; i != S; i = e[pre[i] ^ 1])
            f[pre[i]] -= d[T], f[pre[i] ^ 1] += d[T]; 
    }
    return flow;
}

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", EK());
    return 0;
}

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

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