最大流问题，核心在于添加了反向边，
添加反向边是比较难理解的一部分,作用是让程序有修订的可能,且本次增加的流并不会因为反向边而减少,因为总是从S->T(残余网络)
流和水流性质相似,没有累计和的意思.并没有后面的自身再加流入的.....balabula
注意:
在有向图中边的权值一般+=，因为可能有多条路。无向图是四条边,用邻接表
EK算法
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <queue>
#define maxn 300
using namespace std;
int prev[maxn];
int visited[maxn];
int G[maxn][maxn];
int N,M;
int EK(int source,int terminate)
{
deque<int>heap;
int i,j,k,flag,minnum;
memset(visited,0,sizeof(visited));
memset(prev,0,sizeof(prev));
prev[source]=0;
visited[source]=1;
heap.push_back(source);
flag=0;//用bfs寻找一条源到汇的可行路径，使用双向队列完成
while(!heap.empty())
{
k=heap.front();
heap.pop_front();
for(i=1;i<=terminate;i++)//错误1,循环次数写成了边数
{
if(G[k][i]>0 && visited[i]==0)
{
prev[i]=k;
visited[i]=1;
//minnum=minnum<G[k][i]?minnum:G[k][i]; 错误2,应该在找到完整路径后再求最小值
if(i==terminate)
{flag=1;heap.clear();break;}
heap.push_back(i);
}
if(flag)
break;
}
}
if(flag==0)
return 0;
k=terminate;
minnum=0x7fffffff;//寻找源到汇路径上容量最小的边，其容量就是此次增加的总流量
while(prev[k])
{
minnum=minnum<G[ prev[k]][k]?minnum:G[ prev[k]][k];
k=prev[k];
}
k=terminate;
while(prev[k])
{
G[ prev[k] ][k]-=minnum;
G[k][ prev[k] ]+=minnum;//错误3.应该是添加反向边
k=prev[k];
}
return minnum;
}
int main()
{
int i,s,e,c;
__int64 ans,tmp;
while(scanf("%d%d",&N,&M)!=EOF)
{
memset(G,0,sizeof(G));
for(i=0;i<N;i++)
{
scanf("%d%d%d",&s,&e,&c);
G[s][e]+=c;
}
ans=0;
while(tmp=EK(1,M))
ans+=tmp;
printf("%I64d\n",ans);
}
return 0;
}
Dinic算法
dinic与EK的区别之处在于，EK是用BFS去找增广路，而dinic是在层次图里用DFS找增广路。
基本思路：
1.根据残量网络计算层次图；
2.在层次图中使用DFS进行增广直到不存在增广路；
3.不断重复直到无法增广的时候，算法结束。
所谓的层次图，在残量网络中从源点S起始进行BFS，这样每个顶点在BFS树中就会得到一个距源点s的距离d , 如果d(s) = 0，
直接从s出发可以到达的点距离为1，下一层距离为2，，，，把具有相同距离的顶点放在同一层，在层次图中，
只保留d(i) + 1 = d(j) 的边，这样在层次图中的任意路径就成为到达次顶点的最短路径。
在Dinic算法中，BFS的作用就是判断找的汇点是否在源点开始的层次图中。
接下来的问题是 如何在层次图中使用DFS进行增广？
如果找到一个节点在层次图中，用它往下延伸，一直延伸到汇点，如果存在，就在这条路上找最小容量。如果增广后，容量满了，
阻塞之，实现方法即把这个点在层次图里的编号赋为其它点到不了的值，比如INT_MAX，-1。
如果不能到达汇点，这个节点返回上一层，继续找。
如果这个点都找完后（即上一层到达源点），再BFS从源点建立新的层次图，继续找。。。直到汇点不在新的层次图里结束。
Dicnic模板:
bool bfs(int sp,int tp,int NN){
memset(level,-1,sizeof(level));
queue<int> Q;
Q.push(sp);
level[sp]=0;
while(Q.size()){
int u=Q.front();Q.pop();
for(int v=1;v<=NN;v++) if(cap[u][v] && level[v]==-1){
Q.push(v);
level[v]=level[u]+1;
}
}
return level[tp]!=-1;
}
int extendPath(int sp,int tp,int NN,int u,int beforemin){
int res=0,t;
if(u==tp || beforemin==0) return beforemin;/// 无流量 退出
for(int v=1;v<=NN;v++)
if(cap[u][v] && level[v]==level[u]+1 && (t=extendPath(sp,tp,NN,v,min(beforemin,cap[u][v])))){
cap[u][v]-=t;
cap[v][u]+=t;
beforemin-=t;
res+=t;
if(!beforemin) break;
}
if(!res) level[u]=-1;/// 该点无流量,则去除,加速
return res;/// 使得一次更新多次再回头
}
int Dinic(){
int ans=0,tans;
while(bfs()) while(tans=extendPath(sp,tp,NN,sp,inf)) ans+=tans;
return ans;
}
有下界的网络流
方法:将下界分离
设原图的原点为s，汇点为t，新增原点S，汇点T，对于原图的边(u->v)，从u向T连边，容量为下界，从S向v连边，容量为下界，从u向v连边，容量为上界减下界，从t向s连边，容量为无穷大。备份图G2从S到T跑最大流，如果从S出发的所有边满载，那么可行记此时为sum1，否则不存在.删除S、T之间的边，(其他边不用动,因为流入S流出T都是单向的不影响)然后从s到t跑最大流。sum2.答案是sum1+sum2, 每条边的容量则是G2[i][j]-G[i][j]+low[i][j]
第一次跑最大流直接就是求下界,第二次从s 可流出的流量为剩下的.
先得到high[][] low[][] 再构图high[][]-low[][] OK
最小费用最大流,按照有流量的边情况下用spfa找到最小费用 的路径,(extendPath) loop
int spfa(int sp,int tp,int NN){
queue<int> Q;
memset(vis,0,sizeof(vis));
memset(dist,0x3f,sizeof(dist));
dist[sp]=0;vis[sp]=1;pre[sp]=-1;
Q.push(sp);
while(Q.size()){
int u=Q.front();Q.pop();vis[u]=0;/// u出不再队列中,这里不用计数判断是否有负环
for(int i=head[u];~i;i=node[i].nxt) {
int v=node[i].v;
if(node[i].cap>0 && dist[v]>dist[u]+node[i].cost){
dist[v]=dist[u]+node[i].cost;
pre[v]=i;
if(!vis[v])
vis[v]=1,Q.push(v);/// 不在就入队
}
}
}
return dist[tp]!=inf;
}
int mcmf(int sp,int tp,int NN){
int ans=0,flow_sum=0;
while(spfa(sp,tp,NN)){
int t=inf;
for(int i=pre[tp];i!=-1;i=pre[node[i].u])
t=min(t,node[i].cap);
for(int i=pre[tp];i!=-1;i=pre[node[i].u]){
node[i].cap-=t;
node[i^1].cap+=t;
}ans+= dist[tp]*t;flow_sum+=t;
}
return ans;
}