网络流

update: 2021-4-12 9:58 增加最小割的内容

从我P5192的题解摘过来的

1. 网络流

通俗的讲,网络流就是一个水系,有源点(水库, S )和汇点(大海, T ),中间有很多节点,中间的节点不储存流,作为一个中转站。

每一条边有一个容量(河道宽度),也有一个流量。显然流量小于等于容量。

如图是一张网络流。

一张网络图

已经有流量的图被称为残留网络。

注意:残留网络中,有反向边,而一般认为原图中没有反向边。
反向边的容量是正向边的流量。

(可以这么认为,反向边是用来退回正向边的流量,而最多就退回原来流过的量)

刚才那张图的残留网络是如下:

残留网络

增广路:沿着容量大于0的边,从 S 到达 T 的路径,

(这么多已经足够,详细解释请见百度

2. 最大流

我们现在想要求从源点到汇点能流的最大值。

显然,上面的那张图不是最大流。

最大流应该是这样。

最大流

3. Edmonds-Karp 与 Dinic ——求最大流的算法

Edmonds-Karp 的主要思路是每次寻找一条增广路。

原理可以理解为搜索,直到流不过去为止。

一般能处理$10^3至$10^4的网络规模

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

queue<int> q;

bool bfs()// 广搜
{
for (int i=0;i<N;++i) vis[i]=0;
d[S]=1e8;
while (q.size()) q.pop();
vis[S]=1;
q.push(S);
while (q.size())
{
int x=q.front();q.pop();
for (int i=h[x];i!=-1;i=ne[i])
{
if (vis[e[i]]) continue;
if (w[i]!=0)
{
vis[e[i]]=1;
d[e[i]]=min(d[x],w[i]);
pre[e[i]]=i;//记录前驱
if (e[i]==T) return true;
q.push(e[i]);
}
}
}
return false;
}

int Edmonds_Karp()
{
int r=0;
while (bfs())
{
int f=d[T];
for (int i=T;i!=S;i=e[pre[i]^1])
{
w[pre[i]]-=f;
w[pre[i]^1]+=f;//反向边加上对应流量
}
r+=f;
}
return r;
}

Dinic 是 EK 的优化,主要思想是建立分层图,一次找多个增广路

一般能处理$10^4$至$10^5$的网络规模

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
queue <int> q;

bool bfs()
{
memset(d,-1,sizeof d);
while (q.size()) q.pop();
q.push(S);
d[S]=0;cur[S]=h[S];//cur 是指当前到的出边
while (q.size())
{
int t=q.front();q.pop();

for (int i=h[t];i!=-1;i=ne[i])
{
if (d[e[i]]==-1&&w[i])
{
d[e[i]]=d[t]+1;
cur[e[i]]=h[e[i]];
if (e[i]==T) return true;
q.push(e[i]);
}
}
}
return false;

}

int find(int u,int lim)
{
if (u==T) return lim;
int flow=0;
for (int i=cur[u];i!=-1&&flow<lim;i=ne[i])
{//没有剩余流量就直接退出
cur[u]=i;// 当前弧优化,下一次从这一条边出发
if (d[e[i]]==d[u]+1&&w[i])
{
int t=find(e[i],min(w[i],lim-flow));
if (t!=0) d[e[i]]=-1;
// 没有路径,就不再访问,赋值为-1
w[i]-=t,w[i^1]+=t,flow+=t;
}
}
return flow;
}
int dinic()
{
int r=0,flow=0;
while (bfs())
while (flow=find(S,INF)) r+=flow;
return r;
}

4. 最小割

1) 定义

如果沿着剩余容量大于0的边,无法从 s 到 t,那么这个残余网络就被称为割。

令 s 能搜到的点集合为 S,其余点的集合为 T。

割的容量定义为

割的流量定义为

最小割是指容量最小的割。

2) 最大流最小割定理

当下面条件满足之一时,均满足:

  1. f 是最大流

  2. 不存在从 s 到 t 的路径(沿着剩余容量大于0的边)

  3. 存在一个割,使 $c(S,T)=f(s,t)$

证明:

我们只要证出有1能得到2,有2能得到3,有3能得到1,原命题成立

a.1推2

显然,如果2不满足的话,1一定不满足

他的逆否命题也成立(即原命题)

b.2推3

将 s 能到的点作为一个集合,剩余的作为另一个集合

很明显,现在 S 与 T 的连接一定都是满流,且反向边容量为0

如果感觉有点绕的话,看一下上面的最大流图理解一下

c.3推1

首先,任意一个割,都大于等于最大流。

其次,满足 3 的割,一定大于等于最小割(废话)。

然后,满足 3 的流,一定小于等于最大流。

我们可以得到:$c(S,T) \geq cmin \geq fmax \geq f(s,t)$

又 $c(S,T)=f(s,t)$

所以4项都相等。

证毕。


你已经掌握了最简单的网络流,切切网络流24题吧!


小心被切