网络流
最大流
网络中有两台计算机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：匈牙利算法
京公网安备 11010502036488号