【学习笔记】网络流的简单入门(更新中)

Bn_ff 2020-03-02 21:08:00
原文地址:https://www.cnblogs.com/Bn_ff/p/12398026.html

声明:本博客所有随笔都参照了网络资料或其他博客,仅为博主想加深理解而写,如有疑问欢迎与博主讨论✧。٩(ˊᗜˋ)و✧*。

前言

终于学习到了网络流了其实网络流算法真正难的在于**建模**,如何将问题转化为网络流解决。很多看似和网络流不沾边的题目其实都可用次来解。一入网络流深似海,路漫漫其修远兮

(本篇文章全文主要借鉴这篇blog,写得超级棒哒)


[٩(ˊᗜˋ)و✧* ]

一.概念及性质

网络流基本概念

·网络流:一种类比水流的解决问题方法

·网络:可以看做有源点和汇点的有向图

·弧:有向图的边/水管

·源点:网络中没有入边的点/起点(即可以无限出水的水源),表示为 \(S\)

·汇点:网络中没有出边的点/终点(即可以无限收集水的点),表示为 \(T\)

·容量:一条边可以承受的最大水量,每条边/弧都会有一个容量,表示为函数 \(c(u, v)\)

·流量:一条边当前承受的水量,每条边/弧都会有一个流量,表示为函数 \(f(u, v)\);流量可为 \(0\),可为负

残留容量:一条边还可以新增加的水量,即为 容量 - 流量

·容量网络:每条边都给出了容量的网络

·流量网络:每条边都给出了流量的网络

·残量网络:每条边都给出了残留容量的网络,即为 容量网络 - 流量网络

网络流的三大性质

·容量限制:\(f(u,v)≤c(u,v)\) 一条边的流不能超过它的容量

·流守恒:除非 \(u=s\) 或 \(u=t\) ,否则 \(\sum_{(w∈V)}f(u,w)=0\) 一结点的净流是零,除了“制造”流的源点和“消耗”流的汇点。

(意思就是,除了源点和汇点外,一条边流进来了多少水就会流出去多少水,保证守恒)

·斜对称:\(f(u, v) = -f(v, u)\)

(这个其实也不太好理解...暂时理解为矢量?之后会有很多运用)

[٩(ˊᗜˋ)و✧* ]


[٩(ˊᗜˋ)و✧* ]

二.最大流

概念

·网络的流量:流量网络的汇点收集到的流量值

·最大流:网络的流量的最大值

FF方法

概念

增广路:在残量网络中的一条从 \(S\) 到 \(T\) 的合法路径,即所有弧的残量为正
**
增广路定理:网络达到最大流当且仅当残量网络中没有增广路

\(FF(Ford−Fulkerson)\) 方法又称增广路方法:不断地在残量网络中找到一条从 \(S\) 到 \(T\) 的增广路,向 \(T\) 发送流量,修改此条增广路上弧的残量,直到找不到增广路为止

EK算法

\(EK\):基于 \(FF\) 方法的一种算法

大致流程:

\(1.\)用 \(bfs\) 找一条增广路,逆向记录下这条路上的弧

\(2.\)\(ans\) 加上这条增广路上的流量(木桶定理)

\(3.\)更改此条路径上弧的残量

(细节请看代码)

详细介绍

但是有个问题,就是如何保证我每次随机选择的增广路都是最优的?或者说,是可以达到最大流的,而不会影响后面继续找增广路?

比如下面这张图,第一次找增广路时我们找到了蓝色的这条(\(1 -> 2 -> 3 -> 4\))

![]()

那么下一次我们就无法找出增广路了;可是这就是最大流了吗?

显然不是,如果选择 \(1->2->4\) 和 \(1->3->4\) 最后答案就为 \(2\),比刚才要大

所以我们得给选过的增广路一个反悔的机会

在最初建图时,我们把每条边都建一条流量为\(0\)的反边

选择一条增广路时,除了把这条增广路上弧的残量修改之外,我们还把每条弧的反边加上此次的流量

例如刚才那张图,我们选择了第一条增广路后,它应该变成这样

![]()

接下来我们模拟一下第二次找增广路

首先从 \(1\) 找到了 \(3\),这条弧上残量为正,是合法的

接下来从 \(3\) 开始找,发现可以流向 \(2\),从 \(2\) 又可以流向 \(4\),即找到了一条增广路,\(ans\) 变为 \(2\)

为什么可以这样做?

其实很简单。当我们找到 \(3\) 的时候,和原来那条增广路碰面了,也就是说,从 \(3\) 这里往后走一定会有一条合法的流到达汇点(就是原来那条增广路),于是我们把 \(3\) 以及之后的那条合法路径全部割让给 \(1->3\) 这里, 让 \(2\) 不往 \(3\) 这里走,而是转头去找 \(4\)。

感觉说的有点乱...

引用一段这位大佬写的话

> 将之前流出去的流量的一部分(或者全部)反悔掉了个头,跟随着新的路径流向了其它地方,而新的路径上在到达这条边之前所积蓄的流量 以及 之前掉头掉剩下的流量 则顺着之前的路径流了下去。

时间复杂度

\(O(nm^2)\)

Code

#include<cstdio>
#include<iostream>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#define F(i, x, y) for(register int i = x; i <= y; ++ i)
using namespace std;
int read();
const int N = 1e4 + 5;
const int M = 1e5 + 5;
const int inf = 0x3f3f3f3f;
int n, m, s, t, ans;
int head[N], cnt = 1, ver[M << 1], edge[M << 1], next[M << 1];
int val[N], vis[N], a[N];
queue<int> q;
void add(int x, int y, int z){ver[++ cnt] = y, edge[cnt] = z, next[cnt] = head[x], head[x] = cnt;}
bool bfs()
{
    while(q.size()) q.pop();
    memset(vis, 0, sizeof(vis));
    q.push(s), vis[s] = 1, val[s] = inf;
    while(q.size())
    {
        int x = q.front(); q.pop();
        for(int i= head[x]; i; i = next[i])
            if(edge[i] && ! vis[ver[i]])
            {
                val[ver[i]] = min(edge[i], val[x]);
                q.push(ver[i]), vis[ver[i]] = 1, a[ver[i]] = i;
                if(ver[i] == t) return true;
            }
    }
    return false;
}
void EK()
{
    while(bfs())
    {
        int x = t; ans += val[t];
        while(x != s)
            edge[a[x]] -= val[t], edge[a[x] ^ 1] += val[t], x = ver[a[x] ^ 1];
    }
}
int main()
{
    n = read(), m = read(), s = read(), t = read();
    for(int i = 1, x, y, z; i <= m; ++ i)
        x = read(), y = read(), z = read(), add(x, y, z), add(y, x, 0);
    EK();
    printf("%d", ans);
    return 0;
}
int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return x * f;
}

声明:该文章系转载,转载该文章的目的在于更广泛的传递信息,并不代表本网站赞同其观点,文章内容仅供参考。

本站是一个个人学习和交流平台,网站上部分文章为网站管理员和网友从相关媒体转载而来,并不用于任何商业目的,内容为作者个人观点, 并不代表本网站赞同其观点和对其真实性负责。

我们已经尽可能的对作者和来源进行了通告,但是可能由于能力有限或疏忽,导致作者和来源有误,亦可能您并不期望您的作品在我们的网站上发布。我们为这些问题向您致歉,如果您在我站上发现此类问题,请及时联系我们,我们将根据您的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。