最大流：
算法：
1.Ford_Fulkerson(F_F算法)
2.EK算法
3.dinic算法
EK:
基于暴力搜索思想的方法，每次都采用bfs去寻找从源点到汇点的增广路，直到找不到，即表示找到了最大流，每次找到一条增广路（找的时候记得存下路径）后，可以求出这条路上的最小流量，即为这条增广路的流量。最终流量加上他，再把路径上的每一条边的正向边的流量-最小流量，反向边的流量+最小流量。以此不断的进行，直到最后找不到路。
由于bfs寻找增广路的时间复杂度为O(E),而最多进行O(VE)次查找，所以时间复杂度为O(VE*E)。
EK 算法的实现很简单，当整个图为稀疏图时，EK算法不失为一种简单可行的方法，但如果整个图的边数较多，就不适合了。EK算法每次找到找到增广路后，就从源点重新进行bfs遍历查找增广路，其中有很多的遍历是没有必要的。
代码：
dinic：
在之前算法的基础上，进行优化，基于分层的思想。
每次寻找增广路之前，用bfs去分层，以源点的层数为0，其他的点的层数为该点到源点的距离（以bfs搜索时走的步数，而不是边权值）。当可以分层时，用dfs在已分层的图中进行寻找增广路的操作，直到无法直到无法找到增广路（即该条增广路的流量为0），更改边的相应权值后。再进行bfs分层操作，重复操作。直到不能分层（即汇点不在分层图中），表示已取得最大流。
dinic的当前弧优化：
普通的dinic算法，每次bfs之后都要进行若干次的dfs来寻找增广路，这样就会有某些边会重复查找，当前弧优化就可以避免这个问题，消除不必要的查找，从新的边的开始查找。
用引用的方法，每次找完一次就加，每次从新的地方开始找。
代码（当前弧优化后）：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int inf=0x3f3f3f3f;
struct node
{
int to,val,rev;//边的终点，边的容量，方向边的索引
};
vector<node>pic[N];
queue<int>que;
int layer[N],iter[N];//iter[]数组用于当前弧优化
int n,m,s,t;
bool bfs()
{
for(int i=1;i<=n;i++)
layer[i]=-1;
while(!que.empty())
que.pop();
layer[s]=0;
que.push(s);
while(!que.empty())
{
int a=que.front();
que.pop();
for(int i=0;i<pic[a].size();i++)
{
node b=pic[a][i];
if(layer[b.to]<0&&b.val>0)//layer[]相对于标记
{
layer[b.to]=layer[a]+1;
que.push(b.to);
if(b.to==t)//不用把所有的点都分层，只要分到汇点就行
return true;
}
}
}
return false;
}
int dfs(int a,int c)//
{
if(a==t)
return c;
for(int &i=iter[a];i<pic[a].size();i++)//当前弧优化，已经用过非边不再遍历，引用
{
node &e=pic[a][i];//引用，后面可以直接修改数据
if(e.val>0&&layer[e.to]>layer[a])//只走后面的层次的点
{
int d=dfs(e.to,min(c,e.val))//每次找到一条增广路后，一直回溯到起点，并在此过程中确定路上的最小流量
if(d>0)
{
e.val-=d;
pic[e.to][e.rev].val+=d;//改变时要对原来的信息修改
return d;//返回该条增广路的最大流
}
}
}
return 0;//
}
void dinic()
{
int max_flow=0;
while(bfs())
{
int f=0;
memset(iter,0,sizeof(iter));
while((f=dfs(s,inf))>0)
max_flow+=f;
}
printf("%d\n",max_flow);
}
int main()
{
while(scanf("%d%d%d%d",&n,&m,&s,&t)!=EOF)
{
for(int i=1;i<=n;i++)
pic[i].clear();
int u,v,w;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
pic[u].push_back({v,w,pic[v].size()});
pic[v].push_back({u,0,pic[u].size()-1});
}
dinic();
}
return 0;
}
多路增广优化：
炸点：
最大流最小割定理:最大流=最小割。
求最小割可以用最大流去求。
最小费用最大流：
在最大流的基础上，除了每条边的权值外，还要加上一个费用作为限制。最大流一定的情况下，增广路可能有多种情况。最小费用就要求在最大流的所有方案中找到花费最小的方案。
基本思想：基于EK算法的思想，每次寻找增广路时，以每条边的费用为权值，用最短路算法去寻找花费最小的增广路。再进行EK算法的操作。注意：在记录每条边的权值（费用）时，他的反向边的费用要记为正向边费用的相反数。
1.spfa+EK:
因为有负权边，所以每次寻找花费最小的增广路时可以采用spfa算法来寻找，找到花费最小的增广路。每次算每一条增广路的花费时，用该条增广路的流量*该条增广路的最小花费。
代码：
#include <bits/stdc++.h>
using namespace std;//EK+spfa,每次找增广路时用spfa找从源点到汇点花费最小的路
const int N=5e3+5;
const int inf=0x3f3f3f3f;
typedef pair<int,int> P;
struct node
{
int to,val,cost,rev;//点，边的容量，花费，反向边索引
};
vector<node>pic[N];//
queue<int>que;//不必用priority_queue,用queue就行，用时更少
//priority_queue<P,vector<P>,greater<P> >que;//先比较first，在first相等的情况下比较second
int s,t,n,m;
bool vis[N];
int dis[N],flow[N];//dis[]:表示某一点到源点的最小费用，flow[]表示当前点的路径中最小费用的边的费用
P pre[N];//first:点，second:数组中的序号
bool spfa()
{
while(!que.empty())
que.pop();
for(int i=1;i<=n;i++)
{
vis[i]=false;
dis[i]=inf;
flow[i]=inf;
}
memset(pre,0,sizeof(pre));
dis[s]=0;
que.push(s);
vis[s]=true;
while(!que.empty())
{
int now=que.front();
que.pop();
vis[now]=false;
for(int i=0;i<pic[now].size();i++)
{
node tmp=pic[now][i];
if(dis[tmp.to]>dis[now]+tmp.cost&&tmp.val>0)//最短路松弛
{
dis[tmp.to]=dis[now]+tmp.cost;
pre[tmp.to].first=now;
pre[tmp.to].second=i;
flow[tmp.to]=min(flow[now],tmp.val);//一边找路，一边找最短边
if(!vis[tmp.to])//入队标记，出队取消标记
{
vis[tmp.to]=true;
que.push(tmp.to);
}
}
}
}
if(dis[t]<inf)
return true;
else
return false;
}
void EK()
{
int max_flow=0,min_cost=0;
while(spfa())//如果存在增广路，计算
{
int minn=flow[t];
for(int i=t;i!=s;i=pre[i].first)
{
pic[pre[i].first][pre[i].second].val-=minn;
pic[i][pic[pre[i].first][pre[i].second].rev].val+=minn;
}
max_flow+=minn;
min_cost+=dis[t]*minn;
}
printf("%d %d\n",max_flow,min_cost);
}
int main()
{
while(scanf("%d%d%d%d",&n,&m,&s,&t)!=EOF)
{
for(int i=0;i<=n;i++)
pic[i].clear();
int u,v,w,f;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d%d",&u,&v,&w,&f);
pic[u].push_back({v,w,f,pic[v].size()});
pic[v].push_back({u,0,-f,pic[u].size()-1});
}
EK();
}
return 0;
}
2.dijsktra+EK：
虽然每次寻找花费最小的增广路时，有负权边，但只要进行相应的处理，还是可以使用迪杰斯特拉算法去求最小花费增广路,这样的效率要高于用spfa。
dijsktra算法不能用于负权值网络的原因是因为其使用的是贪心的策略，每次找最短，所以已确定的边不会被负权边所更新。在最大流中，负权边原因是因为正向边有流量通过。
引入势的概念h[x]（表示x到s的最短距离）。
对于一条起点为u,终点为v的边，权值为e(u,v),由dijkstra，及dis数组的含义更新条件有:
dis[v]<=dis[u]+e(u,v)/h[v]<=h[u]+e(u,v);即e(u,v)+dis[u]-dis[v]>=0
因此可以引入势h[u]=dis[u],h[v]=dis[v],e’(u,v)=e(u,v)+h[u]-h[v]>=0;
可以使dis[v]=dis[u]+e.cost+h[u]-h[v],这样dis[]的值就可以保证是非负的;
代码：
#include <bits/stdc++.h>//通过引入势的概念，把负权边转化为正边,用dijkstra寻找增广路
using namespace std;//对于一条起点为u,终点为v的边，权值为e(u,v),由dijkstra
//及dis数组的含义更新条件有:
//dis[v]<=dis[u]+e(u,v);即e(u,v)+dis[u]-dis[v]>=0
//因此可以引入势h[u]=dis[u],h[v]=dis[v],e'(u,v)=e(u,v)+h[u]-h[v]>=0;
const int N=1e5+5;
const int inf=0x3f3f3f3f;
typedef pair<int,int> P;
int dis[N],h[N],flow[N];
P pre[N];//点，序号位置
struct edge
{
int to,val,cost,rev;
};
int n,m;
vector<edge>pic[N];
priority_queue<P,vector<P>,greater<P> > que;//first:边权，second :点
//求解s->t的流量为f的最小费用流
int min_cost_flow(int s,int t,int f)//返回最小费用
{
int res=0;
fill(h,h+n,0);//初始化h
while(f)//f>0时还需要继续增广
{
while(!que.empty())
que.pop();
fill(dis,dis+n,inf);//距离初始化为0
dis[s]=0;
que.push({0,s});
while(!que.empty())
{
P a=que.top();
que.pop();
int v=a.second;
if(dis[v]<a.first)//相当于标记数组
continue;
for(int i=0;i<pic[v].size();i++)
{
edge &e=pic[v][i];
if(e.val>0&&dis[e.to]>dis[v]+e.cost+h[v]-h[e.to])//松弛操作
{
dis[e.to]=dis[v]+e.cost+h[v]-h[e.to];
pre[e.to].first=v;//存路径
pre[e.to].second=i;
que.push({dis[e.to],e.to});
}
}
}
if(dis[t]==inf)//如果dis[t]还是初始时候的值inf,说明s-t不通，无增广路
return -1;
for(int i=0;i<n;i++)//更新h
h[i]+=dis[i];
int d=f;
for(int i=t;i!=s;i=pre[i].first)//找路径上的最小流量
d=min(d,pic[pre[i].first][pre[i].second].val);
f-=d;
res+=d*h[t];
for(int i=t;i!=s;i=pre[i].first)//改变残余量
{
edge &e=pic[pre[i].first][pre[i].second];
e.val-=d;
pic[i][e.rev].val+=d;
}
}
return res;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
//建图
}
return 0;
}
最大流的题目，关键在于建图，利用人为的设置边的流量值，可以达到控制每条边的利用次数的作用，可以把很多意想不到的题目转化为最大流的模型，其反向边的设置，可以提供一个反悔的作用，使得求得的路径最优。可以和二分等算法结合，其中满流的利用，可以用来验证。
常用的建图方法：
1.拆点建图
poj3281----Dining
京公网安备 11010502036488号