网络流
网络流研究的是在复杂网络中信息的传输情况。从一台计算机发出的信息，途径复杂计算机网络最终汇集到介绍端。而网络中的每条线路都有其最大传输容量限制。
网络流算法及其万能，适当的建模后可以解决很多问题，比如二分图问题也可以使用网络流解决(名正言顺的鸽掉了匈牙利算法)。
基本概念：
只介绍一些基本的概念，具体说明和定理证明可以参照博客：xv_rong:网络流
源点：信息/流的出发点
汇点：信息/流的目的地，最终汇集点
弧：弧指代的是网络中的途径，为图中的有向边，分为前向弧和后向弧(跟流的流向是否一致)
弧的容量：弧的容量即传输流量的最大值，用边权指代。
弧的流量：指实际中经过该途径的信息的流量($流量\leqslant容量$)
可行流的流量：每个点流入的流量与流出的流量相等的流叫做可行流。从源点流出的总流量等于汇点接受的总流量。这个值叫做可行流的流量
最大流：可行流流量的最大值
割：割是图G点集的一个子集。如果删去割中的点和与其相连的边，图G分成两个连通分量S、T。此时这个割叫做图G的S-T割
割的容量：S-T所有边的容量之和。容量最小的割被称为最小割
割的流量：S-T实际流过的流量的值。
最大流最小割定理：最大流的流量=最小割的容量
增广路：所有前向弧流量小于容量，后向弧流量大于0(意味着可行流还可以增大)
模板算法(以最大流为例)
Ford-Fulkerson算法
网络流暴力算法之一，几乎肯定被卡……但是理解这个算法是其他更优秀算法的基础。
算法思路：
使用dfs去寻找增广路(从源点到汇点，流量大于0的路径)，找到了就将该路的结果累加到答案中，重复操作直到找不到增广路为止。具体有下面一些核心操作：
反向建边：在dfs过程中，如果一条边e可以组成的增广路流量为d，则令e的边权减少d，同时使得e的反向边e'流量增加d。反向建边的意义在于提供了反悔的机会。
图例
如图，加入A，T连接汇点，C，B链接源点，在第一次搜索时发现路径C->F，且直接使用完流量，但是后续发现C->，B->T的方法更优。但是T的容量已经满了，不能在增加，就可以沿着反向路径T->C->A。它等价于C出发的流量一部分到T，另一部分到A。通过反向路径，使得已经累加到答案中的部分流能尝试通过其他路径(原本已经加到答案中的部分由B->T的流量补偿)
初始化反向边：
在dfs的过程中插入反向边会很麻烦，同时也难以寻找当前便的反向边。因此选择在读入边时直接插入边权为0的反向边，同时记录编号。在算法中，要判断，边权为0的边等价于不存在。
vis[]访问标记：
在dfs过程中，通过标记访问过的节点来避免重复访问。因为如果一个节点被访问过，那么说明从这个点无法找到汇点，不需要重复访问，从而使得每次dfs的复杂度为$O(n)$。每次dfs前vis要初始化。
剩下的细节见代码注释。
模板代码：
// 主要由三部分组成，dfs，算法调用，数据的读入。其中在dfs中要维护数据
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
#define m_p make_pair
#define P pair<int,int>
#define x first
#define y second
typedef long long LL;
typedef unsigned long long ULL;
const LL inf=0x3f3f3f3f3f3f3f3f;
// 洛谷模板题TLE 2个点
struct Edg{
Edg(int vv=0,LL ww=0,int rr=0):v(vv),w(ww),rev(rr){};
int v;
LL w;
int rev;//储存反向边的编号
};
vector<vector<Edg>> edg;//邻接表存边
vector<bool> vis;//dfs时标记点的遍历情况
LL dfs(int u,int target,LL num)
{
if(u==target)
return num;
vis[u]=true;//标记使用过了，不去要去除标记
for(Edg& e:edg[u])
{
if(vis[e.v]==false and e.w>0) //查询没用过的点，边权为0即不存在
{
LL tmp=dfs(e.v,target,min(num,e.w));//最大流有最小容量和最大流量限制
if(tmp>0)//成功找到增广路
{
e.w-=tmp;
edg[e.v][e.rev].w+=tmp;//反向边增加
return tmp;
}
}
}
return 0;
}
LL Ford_Fulkeson(int source,int target)
{
LL flow=0;
LL increment=0;
do{
vis.assign(edg.size()+1,0);
increment=dfs(source,target,inf);//初始流量给的是一个极大值。
flow+=increment;
}while(increment!=0);//dfs知道不存在增广路
return flow;
}
int main()
{
IOS;
#ifdef _DEBUG
freopen("D:/CODE/algorithm_contest/out.txt","w",stdout);
freopen("D:/CODE/algorithm_contest/in.txt","r",stdin);
#elif _LINUX
freopen("/media/linxuan/储存/CODE/algorithm_contest/out.txt","w",stdout);
freopen("/media/linxuan/储存/CODE/algorithm_contest/in.txt","r",stdin);
#endif
int n,m,source,target;
cin>>n>>m>>source>>target;
edg.assign(n+1,vector<Edg>());
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
edg[u].push_back(Edg(v,w,edg[v].size()));
edg[v].push_back(Edg(u,0,edg[u].size()-1));
}
LL ans = Ford_Fulkeson(source,target);
cout<<ans<<endl;
return 0;
}
Dinic 算法
网络里常用算法，加上一点优化后性能优异，很少被卡(拒绝毒瘤出题人)
算法思路：
Dinic算法在FF的基础上，增加了限制。即从源点先跑一边BFS，得到每个点的深度，然后在进行与FF算法类似的过程。在dfs时，只有层次正好+1的边才能访问，其他操作相同。然后在增加了反向弧和减少了正向弧(容量减少到0的点当作去除)的情况下重新跑BFS，重复该过程直到BFS时源点和汇点已经不在联通，即可得到最大流。
当前弧优化：
在一次dfs中，某条边在搜索时为成功搜索到汇点，那么在层次变化(重新BFS)前，重复走该条边也不会得到结果，可以略去。因此使用current[u]来标记当前结点已经遍历到了那条边，遍历过的无用边不会重复访问。由于当前弧优化起到了类似标记的作用，在Dinic算法中就不需要vis标记了。current在每次BFS后更新。
炸点优化：
类似当前弧优化，如果一个点遍历失败了，就把深度赋值为-1来达到永远不要访问的功能。(但是有当前弧的请款下几乎没有作用)
剩下细节看代码注释。
模板代码：
//网络流常用算法，在FF暴力算法的基础上做了一定的优化
// 使用bfs的层数来限制搜索路径的长度，避免绕远路
// 有四部分，dfs，bfs，算法执行，数据读入
// 使用当前弧优化，否则查询太多重复边，时间差距很大 2200ms->16ms
// 由于当前弧已经起到剪枝的作用了，vis加不加影响不大。
#ifndef _USE_MATH_DEFINES
#define _USE_MATH_DEFINES
#endif
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
#define m_p make_pair
#define P pair<int,int>
#define x first
#define y second
typedef long long LL;
typedef unsigned long long ULL;
const LL LLinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
// AC模板
struct Edg{
Edg(int vv=0,LL ww=0,int rr=0):v(vv),w(ww),rev(rr){};
int v;
LL w;
int rev;//储存反向边的编号
};
vector<vector<Edg>> edg;//邻接表存边
vector<int> degree;//BFS的层次
vector<int> current;//当前弧优化，减少“废”边的遍历,记录当前节点遍历到边的编号。
bool BFS(int source,int target)
{
degree.assign(edg.size(),0);
queue<int> que;
que.push(source);
degree[source]=1;
while(!que.empty())
{
int st=que.front();
que.pop();
for(Edg e:edg[st])
{
if(e.w>0 and degree[e.v]==0)
{
degree[e.v]=degree[st]+1;
que.push(e.v);
}
}
}
return degree[target]!=0;//返回图源点和汇点是否连通。
}
LL dfs(int u,int target,LL sum)
{
if(u==target) return sum;
for(int &i=current[u];i<edg[u].size();i++)//这里的i作为当前弧优化要用 引用
{
Edg &e=edg[u][i];
if(e.w>0 and (degree[u]+1)==degree[e.v])//限制条件：相差一层
{
LL tmp=dfs(e.v,target,min(sum,e.w));
if(tmp>0)
{
e.w-=tmp;
edg[e.v][e.rev].w+=tmp;//反向边增加
return tmp;//直接返回，i没有更新，后续仍然可以访问该节点
}
}
}
degree[u]=-1;//当前节点废了，炸点优化，不再使用该点(没啥实际作用)
return 0;
}
LL Dinic(int source,int target)
{
//执行BFS直到不连通，最多n次
LL flow=0;
while(BFS(source,target)==true)
{
current.assign(edg.size(),0);
LL increment=0;
do
{
increment=dfs(source,target,LLinf);
flow+=increment;
} while (increment!=0);
}
return flow;
}
int main()
{
IOS;
#ifdef _DEBUG
freopen("D:/CODE/algorithm_contest/out.txt","w",stdout);
freopen("D:/CODE/algorithm_contest/in.txt","r",stdin);
#elif _LINUX
freopen("/media/linxuan/储存/CODE/algorithm_contest/out.txt","w",stdout);
freopen("/media/linxuan/储存/CODE/algorithm_contest/in.txt","r",stdin);
#endif
int n,m,source,target;
cin>>n>>m>>source>>target;
edg.assign(n+1,vector<Edg>());
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
edg[u].push_back(Edg(v,w,edg[v].size()));
edg[v].push_back(Edg(u,0,edg[u].size()-1));
}
LL ans = Dinic(source,target);
cout<<ans<<endl;
return 0;
}
ISAP算法
在Dinic被卡是可以尝试……
算法思路：
模板代码：
题目练习
飞行员配对问题
解题思路
洛谷网络流24题之一，二分图最大匹配模板问题，要求输出匹配个数和方案。
使用网络流解决二分图问题时(假设集合A与B匹配)，即创造一个指向集合A中所有点的超级源点和B中所有点指向的超级汇点，存在的匹配边权赋值唯一，确保唯一使用。使用模板求解源点到汇点的最大流，几位匹配的最大个数。具体匹配方案可以遍历A中的边，边权为0几位使用了这条边(匹配)，输出即可。
题解代码
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
#define m_p make_pair
#define P pair<int,int>
#define x first
#define y second
typedef long long LL;
typedef unsigned long long ULL;
const int inf=0x3f3f3f3f;
using namespace std;
// 洛谷网络流24题之一，使用网络流解决二分图匹配问题
// AC
// 模板
const LL LLinf=0x3f3f3f3f3f3f3f3f;
struct Edg{
Edg(int vv=0,LL ww=0,int rr=0):v(vv),w(ww),rev(rr){};
int v;
LL w;
int rev;//储存反向边的编号
};
vector<vector<Edg>> edg;//邻接表存边
vector<int> degree;//BFS的层次
vector<int> current;//当前弧优化，减少“废”边的遍历,记录当前节点遍历到边的编号。
bool BFS(int source,int target)
{
degree.assign(edg.size(),0);
queue<int> que;
que.push(source);
degree[source]=1;
while(!que.empty())
{
int st=que.front();
que.pop();
for(Edg e:edg[st])
{
if(e.w>0 and degree[e.v]==0)
{
degree[e.v]=degree[st]+1;
que.push(e.v);
}
}
}
return degree[target]!=0;//返回图源点和汇点是否连通。
}
LL dfs(int u,int target,LL sum)
{
if(u==target) return sum;
for(int &i=current[u];i<edg[u].size();i++)//这里的i作为当前弧优化要用 引用
{
Edg &e=edg[u][i];
if(e.w>0 and (degree[u]+1)==degree[e.v])//限制条件：相差一层
{
LL tmp=dfs(e.v,target,min(sum,e.w));
if(tmp>0)
{
e.w-=tmp;
edg[e.v][e.rev].w+=tmp;//反向边增加
return tmp;//直接返回，i没有更新，后续仍然可以访问该节点
}
}
}
degree[u]=-1;//当前节点废了，炸点优化，不再使用该点(没啥实际作用)
return 0;
}
LL Dinic(int source,int target)
{
//执行BFS直到不连通，最多n次
LL flow=0;
while(BFS(source,target)==true)
{
current.assign(edg.size(),0);
LL increment=0;
do
{
increment=dfs(source,target,LLinf);
flow+=increment;
} while (increment!=0);
}
return flow;
}
void add_edg(int u,int v,LL w){
edg[u].push_back(Edg(v,w,edg[v].size()));
edg[v].push_back(Edg(u,0,edg[u].size()-1));
}
int main()
{
IOS;
#ifdef _DEBUG
freopen("D:/CODE/algorithm_contest/out.txt","w",stdout);
freopen("D:/CODE/algorithm_contest/in.txt","r",stdin);
#elif _LINUX
freopen("/media/linxuan/储存/CODE/algorithm_contest/out.txt","w",stdout);
freopen("/media/linxuan/储存/CODE/algorithm_contest/in.txt","r",stdin);
#endif
int m,n;
cin>>m>>n;
edg.assign(n+m+2,vector<Edg>());
int u,v;
while(cin>>u>>v){
if(u==-1) break;
add_edg(u,v+m,1);
}
for(int i=1;i<=m;i++) add_edg(0,i,1);//超级源点0
for(int i=1;i<=n;i++) add_edg(i+m,m+n+1,1);//超级汇点n+m+1
LL ans=Dinic(0,m+n+1);
cout<<ans<<endl;
// 输出答案只要查看哪些边被用过了就可以了
for(int i=1;i<=m;i++)
{
for(auto e:edg[i])
if(e.w==0 and e.v>m and e.v<=n+m){
cout<<i<<" "<<e.v-m<<endl;
break;
}
}
return 0;
}
