学习总结-网络流

(〇)认识网络流

1.什么是网络

1.1网络的定义

网络是一张有向图。顶点称为节点,边称为图中的每一条边都有一个容量,流经这条边的流量不得超过边的容量。图中还有两个指定的特殊节点,源点\(S\) 以及汇点\(T\)。流量从 \(S\) 流向 \(T\)(\(S\)只出不进,\(T\)只进不出)。

一个网络可以用来模拟道路系统的交通量、管中的液体、电路中的电流或类似一些东西在一个结点的网络中游动的任何事物。

1.2网络的性质

1.2.1流量平衡

引入几个概念:

  • 可行流:通俗地讲,是不超过容量的流
  • 最大流:流量最大的可行流

源点以及汇点,对任意节点有:流入该节点的流量与流出该节点的流量相等。

1.2.2反对称性

引入几个概念:

  • 残量网络:原网络减去某个可行流后的图
  • 増广路:从\(S\)到\(T\)的一条路,并且每一条边的容量都大于0

流量为\(F\),\(F(x,y)=k\)表示从节点\(x\)流向节点\(y\)的流量为\(k\),则有:
\[ F(u,v) = -F(v,u) \]
据此,我们引入反向边。

若边\((u,v)\)有\(f\)的流量,则边\((v,u)\)有\(f\)的容量

(二)最大流

1求解最大流

1.1最大流性质

根据网络的性质可以得到:

如果残量网络上找不到増广路,那么当前流为最大流

如果残量网络上存在増广路,那么当前流一定不是最大流(増广路的流量一定大于0)

1.2\(Edmonds-Karp\) 增广路算法

1.2.1算法流程

该算法是基于上述性质求最大流。

  1. 在网络上用 \(bfs\) 找增广路
  2. 将该增广路上所有的边容量减去路径上能通过的最大流量
  3. 将最大流量累加
  4. 重复以上步骤,直到找不到增广路
1.2.2模板

题目:洛谷P3376 网络最大流

题目描述:如题,给出一个网络图,以及其源点和汇点,求出其网络最大流。

输入格式:

第一行包含四个正整数N、M、S、T,分别表示点的个数、有向边的个数、源点序号、汇点序号。

接下来M行每行包含三个正整数ui、vi、wi,表示第i条有向边从ui出发,到达vi,边权为wi(即该边最大流量为wi)

输出格式:一行,包含一个正整数,即为该网络的最大流。

代码:

//Edmonds-Karp
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4+5, maxm = 1e5+5, INF = 1e9+7;
int head[maxn], ver[maxm*2], edge[maxm*2], Next[maxm*2], tot;
void add(int x,int y,int z)
{
    ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;
    ver[++tot] = x, edge[tot] = 0, Next[tot] = head[y], head[y] = tot;
}
int pre[maxn], incf[maxn], s, t, maxflow;
int n, m;
bool bfs()
{
    bool vis[maxn] = {};
    queue<int> Q;
    Q.push(s);incf[s] = INF;vis[s] = true;
    while(!Q.empty())
    {
        int x = Q.front(); Q.pop();
        for(int i = head[x]; i; i=Next[i])
           if(edge[i])
           {
              int y = ver[i];
              if(vis[y]) continue;
              incf[y] = min(incf[x], edge[i]);
              pre[y] = i;
              Q.push(y), vis[y] = true;
              if( y == t ) return true;
           }
    }
    return false;
}
void update()
{
    int x = t;
    while(x!=s)
    {
        int i = pre[x];
        edge[i] -= incf[t];
        edge[i^1] += incf[t];
        x = ver[i^1];
    }
    maxflow+=incf[t];
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&s,&t);
    tot = 1;
    for(int i=1; i<=m; i++)
    {
        int ui, vi, wi;
        scanf("%d%d%d",&ui,&vi,&wi);
        add(ui, vi, wi);
    }
    while(bfs()) update();
    printf("%d", maxflow);
    return 0;
}

1.3 \(Dinic\)算法

1.3.1算法流程
  1. 先\(bfs\),建好分层图划分节点层次,将节点的深度存在\(d\)数组中
  2. 在分层图上\(dfs\),寻找增广路,并在回溯时更新剩余容量(每个点可以流向多条出边)
  3. 重复以上步骤,直至没有增广路为止
1.3.2模板

题目同1.2.2

代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 10005, maxm = 100005, INF = 1e9;
int head[maxn], ver[maxm<<1], edge[maxm<<1], Next[maxm<<1], tot;
int N, M, S, T, d[maxn];
void add(int x, int y, int z){
    ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;
    ver[++tot] = x, edge[tot] = 0, Next[tot] = head[y], head[y] = tot;
}
bool bfs(){
    for(int i=1; i<=N; i++) d[i] = 0;
    queue<int> Q;
    Q.push(S), d[S] = 1;
    while(!Q.empty()){
        int x = Q.front(); Q.pop();
        for(int i = head[x]; i; i=Next[i]){
            int y = ver[i];
            if(edge[i] and !d[ver[i]]){
                d[y] = d[x] + 1;
                Q.push(y);
                if(y == T) return true;
            }
        }
    }
    return false;
}
int dfs(int x, int flow){
    if(x == T) return flow;
    int rest = flow, k;
    for(int i=head[x]; i and rest; i=Next[i])
        if(edge[i] and d[ver[i]] == d[x]+1){
            k = dfs(ver[i], min(rest, edge[i]));
            edge[i] -= k;
            edge[i^1] += k;
            rest -= k;
        }
    return flow - rest;
}
int main(){
    tot = 1;
    scanf("%d%d%d%d",&N,&M,&S,&T);
    for(int i=1; i<=M; i++){
        int x, y, z;
        scanf("%d%d%d",&x,&y,&z);
        add(x, y, z);
    }
    int maxflow = 0, flow = 0;
    while(bfs()) while(flow = dfs(S, INF)) maxflow += flow;
    printf("%d", maxflow);
    return 0;
}
1.3.3当前弧优化

对于这个,我觉得网上一个大佬讲得很好,这里稍微引用一下。

博文传送门

作者:SDFZ-Floatiy

来源:CSDN

其实是一个很强的优化

每次增广一条路后可以看做“榨干”了这条路,既然榨干了就没有再增广的可能了。但如果每次都扫描这些“枯萎的”边是很浪费时间的。那我们就记录一下“榨取”到那条边了,然后下一次直接从这条边开始增广,就可以节省大量的时间。这就是 当前弧优化 。

具体怎么实现呢,先把链式前向星的head数组复制一份,存进cur数组,然后在cur数组中每次记录“榨取”到哪条边了。

代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 10005, maxm = 100005, INF = 1e9;
int head[maxn], cur[maxn], ver[maxm<<1], edge[maxm<<1], Next[maxm<<1], tot;
int N, M, S, T, d[maxn];
void add(int x, int y, int z){
    ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;
    ver[++tot] = x, edge[tot] = 0, Next[tot] = head[y], head[y] = tot;
}
bool bfs(){
    for(int i=1; i<=N; i++) d[i] = 0, cur[i] = head[i];
    queue<int> Q;
    Q.push(S), d[S] = 1;
    while(!Q.empty()){
        int x = Q.front(); Q.pop();
        for(int i = head[x]; i; i=Next[i]){
            int y = ver[i];
            if(edge[i] and !d[ver[i]]){
                d[y] = d[x] + 1;
                Q.push(y);
                if(y == T) return true;
            }
        }
    }
    return false;
}
int dfs(int x, int flow){
    if(x == T) return flow;
    int rest = flow, k;
    for(int i=cur[x]; i and rest; i=Next[i]){
        cur[x] = i;
        if(edge[i] and d[ver[i]] == d[x]+1){
            k = dfs(ver[i], min(rest, edge[i]));
            edge[i] -= k;
            edge[i^1] += k;
            rest -= k;
        }
    }
    return flow - rest;
}
int main(){
    tot = 1;
    scanf("%d%d%d%d",&N,&M,&S,&T);
    for(int i=1; i<=M; i++){
        int x, y, z;
        scanf("%d%d%d",&x,&y,&z);
        add(x, y, z);
    }
    int maxflow = 0, flow = 0;
    while(bfs()) while(flow = dfs(S, INF)) maxflow += flow;
    printf("%d", maxflow);
    return 0;
}

1.4费用流

费用流其实也不难,无非就是多了个边权。只要将1.2算法中的\(bfs\)改为\(spfa\)即可。

题目:洛谷P3381 最小费用最大流

题目描述

如题,给出一个网络图,以及其源点和汇点,每条边已知其最大流量和单位流量费用,求出其网络最大流和在最大流情况下的最小费用。

输入格式

第一行包含四个正整数N、M、S、T,分别表示点的个数、有向边的个数、源点序号、汇点序号。

接下来M行每行包含四个正整数ui、vi、wi、fi,表示第i条有向边从ui出发,到达vi,边权为wi(即该边最大流量为wi),单位流量的费用为fi。

输出格式

一行,包含两个整数,依次为最大流量和在最大流量情况下的最小费用。

代码

//Edmonds-Karp
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5005, maxm = 50005, INF = 1e9+7;
int head[maxn], ver[maxm<<1], edge[maxm<<1], Next[maxm<<1], cost[maxm<<1], tot;
void add(int x,int y,int z,int w)
{
    ver[++tot] = y, edge[tot] = z, cost[tot] = w, Next[tot] = head[x], head[x] = tot;
    ver[++tot] = x, edge[tot] = 0, cost[tot] = -w, Next[tot] = head[y], head[y] = tot;
}
int pre[maxn], incf[maxn], dis[maxn], s, t, maxflow, ans;
int n, m;
bool spfa()
{
    bool vis[maxn] = {};
    queue<int> Q;
    Q.push(s);incf[s] = INF;vis[s] = true;
    for(int i=1; i<=n; i++) dis[i] = INF;
    dis[s] = 0;
    while(!Q.empty())
    {
        int x = Q.front(); Q.pop();
        for(int i = head[x]; i; i=Next[i])
           if(edge[i])
           {
              int y = ver[i];
              if(dis[y] > dis[x]+cost[i])
              {
                  dis[y] = dis[x]+cost[i];
                  incf[y] = min(incf[x], edge[i]);
                  pre[y] = i;
                  if(!vis[y]) vis[y] = true, Q.push(y);
              }
           }
        vis[x] = false;
    }
    if(dis[t] == INF) return false;
    return true;
}
void update()
{
    int x = t;
    while(x!=s)
    {
        int i = pre[x];
        edge[i] -= incf[t];
        edge[i^1] += incf[t];
        x = ver[i^1];
    }
    maxflow+=incf[t];
    ans+=dis[t]*incf[t];
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&s,&t);
    tot = 1;
    for(int i=1; i<=m; i++)
    {
        int ui, vi, wi, fi;
        scanf("%d%d%d%d",&ui,&vi,&wi,&fi);
        add(ui, vi, wi, fi);
    }
    while(spfa()) update();
    printf("%d %d", maxflow, ans);
    return 0;
}

2题解

2.1 POJ2455 \(Secret Milking Machine\)

题意:给出一张无向图,问从节点\(1\)到节点\(N\)的\(T\)条不重叠的路径中,每条路径中最短的边的最大值是多少。

做法:二分,最大流

思路:看到"最短边的最大值",二话不说,先二分答案。

二分最短边的最大值后,将无用的边(小于该值的边)去掉,得到一张图。

这样容易看出,只要在剩下的图中找到不少于\(T\)的不重叠的路径即可。

考虑网络流,将每条边的容量设置为\(1\),从源点流出无限流量。

求出流到汇点的最大流量,如果大于等于\(T\),就证明有至少\(T\)条不重叠的路径可以到汇点。

代码:

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
const int maxn = 305, maxm = 40005, INF = 2147483647;
int cur[maxn], head[maxn], ver[maxm<<1], edge[maxm<<1], Next[maxm<<1], tot;
int N, P, T, u[maxm], v[maxm], c[maxm];
int s, t, d[maxn];
void add(int x, int y, int z){
    ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;
    ver[++tot] = x, edge[tot] = z, Next[tot] = head[y], head[y] = tot;
}
void Memset(){
    memset(head, 0, sizeof(head));
    memset(Next, 0, sizeof(Next));
    memset(ver, 0, sizeof(ver));
    memset(edge, 0, sizeof(edge));
    tot = 1;
}
bool bfs(){
    for(int i=1; i<=N; i++) d[i] = 0, cur[i] = head[i];
    queue<int> Q;
    Q.push(s), d[s] = 1;
    while(!Q.empty()){
        int x = Q.front(); Q.pop();
        for(int i = head[x]; i; i=Next[i]){
            int y = ver[i];
            if(edge[i] and !d[ver[i]]){
                d[y] = d[x] + 1;
                Q.push(y);
                if(y == t) return true;
            }
        }
    }
    return false;
}
int dfs(int x, int flow){
    if(x == t) return flow;
    int rest = flow, k;
    for(int i=cur[x]; i and rest; i=Next[i]){
        cur[x] = i;
        if(edge[i] and d[ver[i]] == d[x]+1){
            k = dfs(ver[i], min(rest, edge[i]));
            edge[i] -= k;
            edge[i^1] += k;
            rest -= k;
        }
    }
        
    return flow - rest;
}
bool check(int x){
    Memset();
    for(int i=1; i<=P; i++) if(c[i] <= x) add(u[i], v[i], 1);
    int maxflow = 0, flow = 0;
    while(bfs()) while(flow = dfs(s, INF)) maxflow += flow;
    return maxflow >= T;
}
int main(){
    scanf("%d%d%d",&N, &P, &T);
    int l = INF, r = 0;
    s=1, t=N;
    for(int i=1; i<=P; i++){
        scanf("%d%d%d",&u[i], &v[i], &c[i]);
        l = min(l, c[i]);
        r = max(r, c[i]);
    }
    while(l <= r){
        int mid = (l+r)>>1;
        if(check(mid)) r = mid-1;
        else l = mid+1;
    }
    printf("%d", r+1);
    return 0;
}

2.2 POJ2135 \(Farm Tour\)

题意:给出一张无向图,从\(1\)出发到\(N\),找两条不重叠的最短路(和最小),并求出它们的和。

做法:\(spfa\),\(Edmonds-Karp\)

思路:很容易想到如何建边,直接按照题意建边即可,关键是如何找到两条不重叠的最短路径。

有了上一题的经验,发现不重叠这个词,就应该想到网络流。

为了求最短路,自然是网络流中的费用流。

此时,因为题目要求不重叠,所以图中的每条边的容量都为\(1\),费用就是这条路径的长度。

题目又要求要求出两条路径,即流量为\(2\),所以新建一个源点和一个汇点,分别连向\(1\)和\(N\),容量为\(2\),限制容量,保证整张图的最大流是\(2\)(因为图中的所有边的最大流量都是\(1\),保证最大流是\(2\)就是保证了有两条增广路,即两条最短路径)

输出最小费用即可。

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn = 1005, maxm = 20005, INF = 1e9;
int head[maxn], ver[maxm<<1], edge[maxm<<1], cost[maxm<<1], Next[maxm<<1], tot;
int N, M, s, t;
int incf[maxn], pre[maxn], dis[maxn], maxflow, ans;
bool vis[maxn];
void add(int x, int y, int z, int val){
    ver[++tot] = y, edge[tot] = z, cost[tot] = val, Next[tot] = head[x], head[x] = tot;
    ver[++tot] = x, edge[tot] = 0, cost[tot] = -val, Next[tot] = head[y], head[y] = tot;
}
bool spfa(){
    for(int i=1; i<=N; i++) dis[i] = INF, vis[i] = false;
    queue<int> Q;
    Q.push(s);
    dis[s] = 0; incf[s] = INF; vis[s] = true;
    while(!Q.empty()){
        int x = Q.front(); Q.pop(); vis[x] = false;
        for(int i=head[x]; i; i=Next[i])
            if(edge[i]){
                int y = ver[i];
                if(dis[x] + cost[i] < dis[y]){
                    dis[y] = dis[x] + cost[i];
                    incf[y] = min(incf[x], edge[i]);
                    pre[y] = i;
                    if(!vis[y]) vis[y] = true, Q.push(y);
                }
            }
    }
    if(dis[t] == INF) return false;
    return true;
}
void update(){
    int x = t;
    while(x != s){
        int i = pre[x];
        edge[i] -= incf[t];
        edge[i^1] += incf[t];
        x = ver[i^1];
    }
    maxflow += incf[t];
    ans += incf[t]*dis[t];
}
int main(){
    scanf("%d%d",&N,&M);
    tot = 1, s = N+1, t = N+2;
    for(int i=1; i<=M; i++){
        int x, y, cost;
        scanf("%d%d%d",&x,&y,&cost);
        add(x, y, 1, cost);
        add(y, x, 1, cost);
    }
    N += 2;
    add(s, 1, 2, 0);
    add(N-2, t, 2, 0);
    while(spfa()) update();
    printf("%d",ans);
    return 0;
}

2.3 POJ3680 $Intervals $

题意:给出\(N\)个开区间,每个区间都有一个权值。只能允许最多\(K\)个区间重叠。求最大的区间权值和。

做法:\(spfa\),\(Edmonds-Karp\),离散化

思路:这题很难想,直接说如何建图了。

将区间的所有端点排好序,列成一条直线(类似于数轴的东西)。

然后在最前端建立一个源点,在最末端建立一个汇点。

将所有点按前到后的顺序依次连边,除源点和汇点连接的那两条边外,其他边的容量为无限,花费为0.

源点和汇点的那两条边容量为\(K\),花费为0。

以上的都很好理解,重头戏来了。

将原先区间的左右端点相连,容量为1,花费为区间权值。

按照以上所述,可以自己动手画一张图,有助于理解。

可以直观地看出,如果两个区间有重叠(假设是区间\(A\)和\(B\)),那么在区间\(A\)必有区间\(B\)的端点。

由此可以推测,如果区间\(A\)与\(x\)个区间有重叠,那么区间\(A\)中必定有\(x\)个其他区间的端点。

到这里,就可以发现,要控制\(A\)最多与多少个区间重叠,只需要控制流经区间\(A\)的流量,与区间\(A\)重叠的区间数不会大于流量,因为每流经一个其他区间,\(A\)区间的流量数便减1。

这也是前面提到的限制源点到汇点的流量为\(K\)的原因。

然后根据以上建图,跑个费用流即可(注意,是求最大费用,因此区间权值可以取相反数,套模板)

代码:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn = 1505, maxm = 2005, INF = 1e9+7;
int head[maxn], ver[maxm<<1], edge[maxm<<1], cost[maxm<<1], Next[maxm<<1], tot;
int N, K, Left[maxn], Right[maxn], lenth[maxn], seq[maxn<<1], key[maxn<<1];
int s, t, ans, incf[maxn], pre[maxn], dis[maxn];
void add(int x, int y, int z, int val){
    ver[++tot] = y, edge[tot] = z, cost[tot] = val, Next[tot] = head[x], head[x] = tot;
    ver[++tot] = x, edge[tot] = 0, cost[tot] = -val, Next[tot] = head[y], head[y] = tot;
}
bool spfa()
{
    bool vis[maxn] = {};
    queue<int> Q;
    Q.push(s);incf[s] = INF;vis[s] = true;
    for(int i=1; i<=t; i++) dis[i] = INF;
    dis[s] = 0;
    while(!Q.empty())
    {
        int x = Q.front(); Q.pop();
        for(int i = head[x]; i; i=Next[i])
           if(edge[i])
           {
              int y = ver[i];
              if(dis[y] > dis[x]+cost[i])
              {
                  dis[y] = dis[x]+cost[i];
                  incf[y] = min(incf[x], edge[i]);
                  pre[y] = i;
                  if(!vis[y]) vis[y] = true, Q.push(y);
              }
           }
        vis[x] = false;
    }
    if(dis[t] == INF) return false;
    return true;
}
void update()
{
    int x = t;
    while(x!=s)
    {
        int i = pre[x];
        edge[i] -= incf[t];
        edge[i^1] += incf[t];
        x = ver[i^1];
        
    }
    ans+=dis[t]*incf[t];
}
int main(){
//  freopen("eeeeeee.txt","w",stdout);
    int G;
    scanf("%d",&G);
    while(G--){
        tot = 1; ans = 0;
        memset(head, 0, sizeof(head));
        memset(Next, 0, sizeof(Next));
        scanf("%d%d",&N,&K);
        for(int i=1; i<=N; i++){
            int l, r;
            scanf("%d%d%d",&Left[i], &Right[i],&lenth[i]);
            if(Left[i] > Right[i]) swap(Left[i], Right[i]);
            seq[i] = Left[i], seq[i+N] = Right[i];
        }
        sort(seq+1, seq+2*N+1);
        int rak = 0;
        for(int i=1; i<=2*N; i++)
            if(seq[i] != seq[i-1]) key[++rak] = seq[i];
        for(int i=1; i<=N; i++){
            for(int j=1; j<=rak; j++){
                if(Left[i] == key[j]) Left[i] = j;
                if(Right[i] == key[j]) Right[i] = j;
            }
        }
        s = rak+1, t = rak+2;
        add(s, 1, K, 0); add(rak, t, K, 0);
        for(int i=1; i<rak; i++) add(i, i+1, INF, 0);
        for(int i=1; i<=N; i++) add(Left[i], Right[i], 1, -lenth[i]);
        while(spfa()) update();
        printf("%d\n", -ans);
    }
    return 0;
}
上一篇:单源最短路的综合应用


下一篇:JavaScript用户代理字符串检测脚本