网络流

最大流

网络中有两台计算机s和t，现在想从s传输数据到t。称使得传输量最大的f为最大流，而求解最大流的问题为最大流问题。此外，我们称c为边的容量，f为边的流量，s为源点(source)，t为汇点(sink)。

Ford-Fulkerson算法

1️⃣只利用满足f(e)<c(e)的e或者2️⃣满足f(e)>0的e对应的反向边rev(e)，寻找一条s到t的路径。
如果不存在满足条件的路径，则结束。否则，沿着该路径尽可能地增加流，返回第1步

称1中所考虑的满足f(e)<c(e)的e和满足f(e)>0的 e对应的反向边rev(e)所组成的图为残余网络，并称残余网络上的 s-t 路径为增广路。

当然，看完这个肯定是一脸懵逼，不要放弃，懵懵懂懂总比完全不懂好😊

（2019.7.16号：再看感觉有点懂了，理解书上P211上方的贪心算法和正确算法的流量的差，其核心是每次找s到t的路径时，s到t的总路径都是增加的，所以无论是通过1️⃣方式还是2️⃣方式找到）

前向弧：弧的方向与路的方向一致，前向弧的全体记为P+
后项弧：弧的反向与路的方向相反，后项弧的全体记为P-
设f是一个可行流，P是从s到t的一条路，若P满足一下条件：
- P中所有的前向弧都是非饱和弧
- P中所有的后向弧都是非零弧
  则称P为关于可行流f的一条增广路
残余网络：有增广路的网络
增广路定理：当且仅当残余网络中没有增广路时，网络达到最大流

形象图解

初始网络（求 A\to C的最大流）
若从若从A\to B\to D\to C开始贪心，最终结果为4
每增广一次，就建立一条反向边，在对A\to B\to D\to C增广后：

注意这里的A′B′C′D并不是虚点，而是ABCD本身，这里只是为了方便画图和观察所以分开画了。
我们发现A\to D\to B\to C变得可增广了：

继续扫一遍，发现A\to D\to C还可以增广，于是最终结果为6：

Ford-Fulkerson算法

下面是一个Ford-Fulkerson算法的邻接表实现的例子。这里没有保存f(e)的值，取而代之的是直接改变c(e)的值。

记最大流的流量为F，那么Ford-Fulkerson算法最多进行F次深度优先搜索，所以其复杂度为O(F|E|)。不过这是一个很松的上界，达到这种最坏复杂度的情况几乎不存在。所以在多数情况下，即便通过估算得到的复杂度偏高，实际运用当中也是比较快的。

//用于表示边的结构体(终点、容量、反向边)
struct edge
{
    int to,cap,rev;//这里的rev表示它对应的反向边的标号
};

vector<edge> G[MAX_V];//图的邻接表表示
bool used[MAX_V];//DFS中用到的访问标记

//向图中增加一条从s到t容量为cap的边
void add_edge(int from ,int to,int cap){
    G[from].push_back((edge){to,cap,G[to].size()});
    /*
    即G[from][j]对应的反向边在G[to]中是第当前的G[to].size()个
    如当前G[from]增加了一个边，记录它的反向边为G[to]中的第G[to].size()，、
    然后在下一条语句中，就会将该边加入到G[to]当中
    */
    G[to].push_back((edge){from,0,G[from].size()-1});
}

//通过DFS寻找增广路
int dfs(int v,int t,int f){
    if(v==t) return f;
    used[v]=true;//v为起点，已使用过
    for(int i=0;i<G[v].size();i++){
        edge &e=G[v][i];
        if(!used[e.to] && e.cap>0){
            int d=dfs(e.to,t,min(f,e.cap));
            if(d>0){
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;
}

//求解从s到t的最大流
int max_flow(int s,int t){
    int flow=0;
    for(;;){
        memset(used,0,sizeof(used));
        int f=dfs(s,t,INF);
        if(f==0) return flow;
        flow+=f;
    }
}

Dinic算法

Ford-Fulkerson算法是通过深度深度优先搜索寻找增广路，并沿它着它增广。与之相对，Dinic算法总是寻找最短的增广路，并沿着它增广。因为最短增广路的长度在增广过程中始终不会变短，所以无需每次都通过宽度预先搜索来寻找最短增广路。我们可以先进行一次宽度优先搜索，然后考虑由近距离顶点指向远距离顶点的边所组成的分层图，在上面进行深度优先搜索寻找最短增广路。如果在分层图上找不到新的增广路了，则说明最短增广路的长度确实变长了，或不存在增广路了，于是重新通过宽度优先搜索构造新的分层图。每一步构造分层图的复杂度为O(|E|)，而每一步完成之后最短路的长度都会至少增加1，由于增广路的长度不会超过|V|-1，因此最多重复O(|V|)步就可以了。

struct edge{
    int to,cap,rev;
};

vector<edge> G[MAX_V];
int level[MAX_V];//顶点到源点的距离标号
int iter[MAX_V];//当前弧，在其之前的边已经没有用了

//向图中增加一条从from到to的容量为cap的边
void add_edge(int from,int to,int cap){
    G[from].push_back(edge{to,cap,G[to].size()});
    G[to].push_back(edge{from,0,G[from].size()-1});
}

//通过BFS计算从源点出发的距离编号(这样可以在DFS跑最短路时指明方向)
void bfs(int s){
    memset(level,-1,sizeof(level));
    queue<int> que;
    level[s]=0;
    que.push(s);
    while(!que.empty()){
        int v=que.front();que.pop();
        for(int i=0;i<G[v].size();i++){
            edge &e=G[v][i];
            if(e.cap>0&&level[e.to]<0){//加入最短路中的条件：1.没有访问过的 2.边还可增广的
                level[e.to]=level[v]+1;
                que.push(e.to);
            }
        }
    }
}

//通过DFS寻找增广路
int dfs(int v,int t,int f){
    if(v==t) return f;
    for(int &i=iter[v];i<G[v].size();i++){//也会发生iter[v]++，这样不会每次都从0开始，是弧优化
        edge &e=G[v][i];
        if(e.cap>0&&level[v]<level[e.to]){
            int d=dfs(e.to,t,min(f,e.cap));//边e能通过的最大流
            if(d>0){
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;
}

//求解从s到t的最大流
int max_flow(int s,int t){
    int flow=0;
    for(;;){//每次最短增广路的长度都会增加1，由于增广路的长度不会超过|V|-1，循环次数为O(|V|)
        bfs(s);//即BFS的复杂度为O(|E|)
        if(level[t]<0) return flow;//说明没有可到达t的增广路
        memset(iter,0,sizeof(iter));
        while((f=dfs(s,t,INF))>0) flow+=f;//复杂度为O(|E||V|)
    }
}

最大流的各种变体

多个源点和汇点的情况
如果有多个源点和汇点，并且它们都有对应的最大流出容量和流入容量限制时，增加一个超级源点s和超级汇点t，从s向每一个源点连一条容量为对应最大流出容量的边，从每一个汇点向t连一条容量为对应最大流入容量的边。
无向图的情况
考虑无向图的情况，此时容量表示的是两个方向流量之和的上界。最大流中没必要在两个方向都有流量，因此把无向图中容量为c的一条边当作有向图中两个方向各有一条容量为c的两条边，就能够得到同样的效果。
顶点上也有容量限制的情况
将每个顶点拆成两个。拆点之后得到入顶点和出顶点，再从入顶点向出顶点连容量为原先顶点限制的边，就可以把顶点上的容量限制转为边上的容量限制了。

最小割

所谓图的割，指的是对于某个顶点集合S\subset V，从S出发指向S外部的那些边的集合，记为割(S,V\backslash S)。这些边的容量之和被称为割的容量。如果有s\in S，而t\in V\backslash S，那么这时的割又称为s-t割。如果将网络中s-t割所包含的边都删去，也就不会有从s到t的路径了。因此，可以考虑一下如下问题。

对于给定网络，为了保证没有从s到t的路径，需要删除的边的总容量的最小值是多少？

该问题有被称为最小割问题。

首先，让我们考虑一下任意的s-t流f和任意的s-t流(S,V\S)。因为有(f的流量)=(s的出边的总流量)，而对v\subset S\backslash {s}又有(v的出边的总流量)=(v的入边的总流量)，所以有(f的流量)=(S的出边的总流量)-(S的入边的总流量)。由此可知(f的流量)\leq(割的流量)。

二分图匹配

指派问题

有N台计算机和K个任务。我们可以给每台计算机分配一个任务，每台计算机能够处理的任务种类各不相同。求最多能够处理的任务的个数。

二分图匹配常常在指派问题的模型中出现。

实际上，可以将二分图匹配问题看成是最大流问题的一种特殊情况，将无向边改为有向边，方向从计算机顶点集合U指向任务集合V，容量为1，并增加源点s和汇点t。

#include<bits/stdc++.h>
using namespace std; 
int N,K;
bool can[MAXN][MAXK];//can[i][j]:=计算机i能处理任务j

void solve(){
    //0-N-1:计算机对应的顶点
    //N-N+K-1:任务对应的顶点
    int s=N+K,t=s+1;

    //在源点和计算机之间连边    
    for(int i=0;i<N;i++){
        add_edge(s,i,1);
    }

    //在任务和汇点之间连边
    for(int i=0;i<K;i++){
        add_edge(N+i,t,1);
    }

    //在计算机和任务之间连边
    for(int i=0;i<N;i++){
        for(int j=0;j<K;j++){
            if(can[i][j]) add_edge(i,N+j,1);
        }
    }

     printf("%d\n",max_flow(s,t));
}

最小费用流

最小传输费用

网络中有两台计算机s和t，现在每秒钟要从s传输大小为F的数据到t。该网络中一共有N台计算机，其中一些计算机之间连有一条单向的通信电缆，每条通信电缆都有对应的1秒钟内所能传输的最大数据量x和单位传输费用d，需要花费的费用为dx。问传输数据所需的最小费用。

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
#define INF 0x3f3f3f3f
#define MAXV 1000
//表示边的结构体(终点、容量、费用、反向边)
struct edge
{
    int to,cap,cost,rev;
};
int V;//顶点数
vector<edge> G[MAXV];//图的邻接表表示
int dist[MAXV];//最短距离
int prevv[MAXV],preve[MAXV];//最短路中的前驱节点和对应的边

//向图中增加一条从from到to容量为cap费用为cost的边
void add_edge(int from,int to,int cap,int cost){
    G[from].push_back((edge){to,cap,cost,G[to].size()});
    G[to].push_back((edge){from,0,-cost,G[from].size()-1});
}

//求解从s到t流量为f的最小费用流
//如果不能再增广则返回-1
int min_cost_flow(int s,int t,int f){
    int res=0;
    while(f>0){
        //利用Bellman-Ford算法求从s到t的最短路
        fill(dist,dist+V,INF);
        dist[s]=0;
        bool update=true;
        while(update){
            update=false;
            for(int v=0;v<V;v++){
                if(dist[v]==INF) continue;
                for(int i=0;i<G[v].size();i++){
                    edge &e=G[v][i];
                    if(e.cap>0&&dist[e.to]>dist[v]+e.cost){
                        dist[e.to]=dist[v]+e.cost;
                        prevv[e.to]=v;
                        preve[e.to]=i;
                        update=true;
                    }
                }
            }    
        }

        if(dist[t]==INF){
            ///不能再增广
            return -1;
        }

        //沿s到t的最短路尽量增广
        int d=f;
        for(int v=t;v!=s;v=prevv[v]){
            d=min(d,G[prevv[v]][preve[v]].cap);
        }
        f-=d;
        res+=d*dist[t];
        for(int v=t;v!=s;v=prevv[v]){
            edge &e=G[prevv[v]][preve[v]];
            e.cap-=d;
            G[v][e.rev].cap+=d;
        }
    }
    return res;
}

版子题： POJ-3068 "Shortest" pair of paths

{% fold 查看代码%}

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
#define INF 0x3f3f3f3f
#define MAXV 200
//表示边的结构体(终点、容量、费用、反向边)
struct edge
{
    int to,cap,cost,rev;
};
int V;//顶点数
vector<edge> G[MAXV];//图的邻接表表示
int dist[MAXV];//最短距离
int prevv[MAXV],preve[MAXV];//最短路中的前驱节点和对应的边

//向图中增加一条从from到to容量为cap费用为cost的边
void add_edge(int from,int to,int cap,int cost){
    G[from].push_back((edge){to,cap,cost,G[to].size()});
    G[to].push_back((edge){from,0,-cost,G[from].size()-1});
}

//求解从s到t流量为f的最小费用流
//如果不能再增广则返回-1
int min_cost_flow(int s,int t,int f){
    int res=0;
    while(f>0){
        //利用Bellman-Ford算法求从s到t的最短路
        fill(dist+1,dist+2*V,INF);
        dist[s]=0;
        bool update=true;
        while(update){
            update=false;
            for(int v=1;v<2*V;v++){
                if(dist[v]==INF) continue;
                for(int i=0;i<G[v].size();i++){
                    edge &e=G[v][i];
                    if(e.cap>0&&dist[e.to]>dist[v]+e.cost){
                        dist[e.to]=dist[v]+e.cost;
                        prevv[e.to]=v;
                        preve[e.to]=i;
                        update=true;
                    }
                }
            }    
        }

        if(dist[t]==INF){
            ///不能再增广
            return -1;
        }

        //沿s到t的最短路尽量增广
        int d=f;
        for(int v=t;v!=s;v=prevv[v]){
            d=min(d,G[prevv[v]][preve[v]].cap);
        }
        f-=d;
        res+=d*dist[t];
        for(int v=t;v!=s;v=prevv[v]){
            edge &e=G[prevv[v]][preve[v]];
            e.cap-=d;
            G[v][e.rev].cap+=d;
        }
    }
    return res;
}

int main(){
    int m;
    int t=1;
    while(cin>>V>>m&&V+m!=0){
        memset(G,0,sizeof(G));
        memset(dist,0,sizeof(dist));
        memset(prevv,0,sizeof(prevv));
        memset(preve,0,sizeof(preve));
        int from,to,cap,cost;
        for(int i=0;i<m;i++){
            cin>>from>>to>>cost;
            add_edge(from*2+1,to*2,1,cost);
            add_edge(to*2,to*2+1,1,0);
        }
        cout<<"Instance #"<<t++<<": ";
        int res=min_cost_flow(1,2*V-1,2);
        if(res==-1) cout<<"Not possible"<<endl;
        else cout<<res<<endl;
    }
    return 0;
}

{% endfold %}

网络流24题

P2756 飞行员配对方案问题

经典二分图匹配问题：

解题报告1：Ford-Fulkerson算法+增加超级源点超级汇点

解题报告2：匈牙利算法