登录/注册
Web前端之巅
2185
占位
2
占位
0
浏览量
占位
粉丝
占位
关注
【网络流】网络流基本概念
Web前端之巅
2021-06-24 16:30:11 2021-06-24
115
0

网络流涉及到的概念好多

(qwq)

，梳理一下。

流网络

流网络是一个有向图，包含点集和边集。即

(G=(V,E))

。
对于边

(e:u\rightarrow v)

（也可以记为

((u,v))

），有属性

(c(u,v))

，称为容量。可以将其比喻为水管在单位时间可以流过的最大水量。

而图

(G)

中有两个特殊的点，称为源点和汇点，通常记为

(s)

,

(t)

，可以将源点比喻为无限的水源，将汇点比喻为能够容纳无穷的水的容器。

可行流

我们记

(f(u,v))

为边

(e:u\rightarrow v)

当前的流量，流量需要满足两个约束：

  1. 容量限制：即

(0 \leq f(u,v) \leq c(u,v))

  1. 流量守恒：除了源点、汇点，其他点流入的流量等于流出的流量，正式地说：

(\sum_{(u,x) \in E} f(u,x) = \sum_{(x,v)\in E)} f(x,v))

流量值

用单位时间流出源点的流量来刻画，记为

(|f|=\sum_{(s,x) \in E} f(s,x) - \sum_{(y,s)\in E)}f(y,s))

。

最大流

又称为最大可行流，即对于

(G)

中可行流构成的集合中，流量值最大的元素。

残留网络

又称为残量网络，注意，残留网络总是针对原图

(G=(V,E))

中的某一个可行流而言的，因此，可以残留网络看成是可行流的一个函数，通常记为

(G_f)

。

(G_f=(V_f,E_f)) ，其中

(V_f=V)

，

(E_f=E和E中所有的反向边)

。

残留网络中的容量记为

(c'(u,v))

，定义为：

[ c'(u,v)=\left{ \begin{matrix} c(u,v)-f(u,v) && (u,v) \in E \ f(v,u) && (v,u) \in E \end{matrix} \right. ]

增广路径

如果从源点

(s)

出发沿着残留网络中容量大于

(0)

的边走，可以走到汇点

(t)

，那么将走过的边所组成的路径称为增广路径。

原网络可行流+残留网络可行流也是原网络的一个可行流

正式地说，

(f+f')

属于

(G)

的一个可行流，且有

(|f+f'|=|f|+|f'|)

。

割

是网络中顶点的一个划分，把所有顶点划分成两个顶点集合

(S)

和

(T)

，其中源点

(s)

属于

(S)

，汇点

(t)

属于

(T)

，而且有

(S \cup T=V)

，

(S \cap T=\emptyset)

，记为

([S,T])

。

割的容量

(c(S,T)=\sum_{u\in S}\sum_{v\in T}c(u,v))

最小割

(G) 中所有割组成的集合中，容量最小的元素。

割的流量

(f(S,T)=\sum_{u\in S}\sum_{v\in T}f(u,v) - \sum_{u\in T}\sum_{v\in S}f(u,v))

任意割的流量

(\leq)

容量

正式地说，即

(\forall [S,T])

，

(f(S,T)\leq c(S,T))

。

证明：（待补充）

最大流最小割定理

  1. (f) 是最大流
  2. (G_f) 不存在增广路
  3. (\exists [S,T]) ，满足

(|f|=c(S,T))

最大流最小割定理指的是：上面的三个命题是等价的。（也就是说可以互推）。

证明：

  • 先证明 1 可以推得 2 ：
    反证即可，如果

(G_f)

存在增广路，那么原图

(G)

中存在流量大于

(0)

的可行流

(|f'|)

，那么

(f+f')

也是可行流，且流量为

(|f|+|f'|>|f|)

，矛盾。

  • 下证 2 可以推得 3 ：
    我们将对于

(G_f)

中从

(s)

出发沿着容量大于

(0)

的边可以到达的点全部放入集合

(S)

中，然后令

(T=V-S)

。
那么对于点

(x \in S)

，

(y \in T)

，边

((x,y))

一定有

(f(x,y)=c(x,y))

。
而对于点

(x \in T)

，

(y \in S)

。必然有

(f(x,y)=0)

。因而割可以被构造出来。

  • 最后证明 3 可以推得 1 ：
    因为

(|f|\leq 最大流 \leq c(S,T))

，而由 3 可知

(|f|=c(S,T))

，故上式取等，即有

(f)

是最大流。

最大流FF方法

基于这样的思路：

  1. 寻找增广路
  2. 利用增广路更新残留网络

一直这样做，直到找不到增广路，那么即可求得最大流。

算法：

单路增广：EK算法

#include<bits/stdc++.h>
using namespace std;
const int INF=1e9;
const int N=1005, M=10010;
int n, m, S, T;
struct node{
    int to, c, next;
}e[M<<1];
int h[N], tot;
// 残量网络建图，初始时正向的容量是 c, 反向容量是 0 。
void add(int u, int v, int c){
    e[tot].to=v, e[tot].c=c, e[tot].next=h[u], h[u]=tot++;
    e[tot].to=u, e[tot].c=0, e[tot].next=h[v], h[v]=tot++;    
}
int lim[N], pre[N]; // lim[u] 表示 S 到点 u 路径容量的最小值， pre[u] 表示 u 的前驱边。
bool vis[N];
int q[N];
// bfs 找增广路。
bool bfs(){
    memset(vis, false, sizeof vis);
    int hh=0, tt=-1;
    q[++tt]=S, vis[S]=true, lim[S]=INF;
    
    while(tt>=hh){
        int hd=q[hh++];
        for(int i=h[hd]; ~i; i=e[i].next){
            int go=e[i].to;
            if(vis[go] || !e[i].c) continue;
            vis[go]=true, q[++tt]=go;
            lim[go]=min(lim[hd], e[i].c);
            pre[go]=i;
            if(go==T) return true;
        }
    }
    return false;
}
int EK(){
    int res=0;
    while(bfs()){
        res+=lim[T];
        for(int i=T; i!=S; i=e[pre[i]^1].to){
            e[pre[i]].c-=lim[T], e[pre[i]^1].c+=lim[T];
        }
    }
    return res;
}
int main(){
    memset(h, -1, sizeof h);
    cin>>n>>m>>S>>T;
    while(m--){
        int u, v, c; cin>>u>>v>>c;
        add(u, v, c);
    }    
    cout<<EK()<<endl;
    return 0;
}

多路增广：dinic算法

代码：

#include<bits/stdc++.h>
using namespace std;
#define gc() (st==ed&&(ed=(st=buf)+fread(buf,1,100000,stdin),st==ed)?EOF:*st++)
char buf[100001],*st=buf,*ed=buf;
void read(int &a){
    a=0;char c=gc();
    while(c>'9'||c<'0')c=gc();
    while(c>='0'&&c<='9')a=a*10+c-48,c=gc();
}
const int INF=0x3f3f3f3f;
const int N=10010, M=1e5+5;
struct node{
    int to, c, next;
}e[M<<1];
int h[N], tot;
void add(int u, int v, int cap){
    e[tot].to=v, e[tot].c=cap, e[tot].next=h[u], h[u]=tot++;
    e[tot].to=u, e[tot].c=0, e[tot].next=h[v], h[v]=tot++;  
}
int n, m, S, T;
int d[N], q[N], cur[N];
bool bfs(){
    memset(d, -1, sizeof d);
    int tt=-1, hh=0;
    q[++tt]=S, d[S]=0, cur[S]=h[S];
    while(tt>=hh){
        int hd=q[hh++];
        for(int i=h[hd]; ~i; i=e[i].next){
            int go=e[i].to;
            if(d[go]==-1 && e[i].c){
                d[go]=d[hd]+1;
                cur[go]=h[go];
                if(go==T) return true;
                q[++tt]=go;
            }
        }
    }
    return false;
}
int find(int u, int limit){
    if(u==T) return limit;
    int flow=0;
    for(int i=cur[u]; ~i && flow<limit; i=e[i].next){
        cur[u]=i;
        int go=e[i].to;
        if(d[go]==d[u]+1 && e[i].c){
            int t=find(go, min(e[i].c, limit-flow));
            if(!t) d[go]=-1;
            e[i].c-=t, e[i^1].c+=t, flow+=t;
        }
    }
    return flow;
}
int dinic(){
    int res=0, flow;
    while(bfs()) while(flow=find(S, INF)) res+=flow;
    return res;
}
int main(){
    memset(h, -1, sizeof h);
    read(n), read(m), read(S), read(T);
    while(m--){
        int u, v, cap; read(u), read(v), read(cap);
        add(u, v, cap);
    }
    cout<<dinic()<<endl;
    return 0;
}

原文: https://www.cnblogs.com/Tenshi/p/14706721.html

暂无评论