学习总结-网络流

2024-03-28 20:57:28

(〇)认识网络流

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用户代理字符串检测脚本