最大流就是建一个反向边，所以说正向边加反向边之和就等于你一开始输入的值，然后找一条增广路，找出最小的cos，把最大流tot加上cos，然后正向边减cos，反向边加cos，这样可以修正错误，因为其实你不用这样流，可你这样流了，就这样直到找不到增广路，就找不到更多的流量了，这时的值就是最大的，其实就是一次一次添流量，直到不能添了
1.EK（Edmond—Karp）算法
也就是广搜版
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int M=1999999,INF=999999999;
int n,m,s,t,used[M];
int f[10999][10999];
int a[M],pre[M];int d[M];
int bfs(int s,int t){
int flow=0;
while(1){
memset(a,0,sizeof(a));
memset(d,0,sizeof(d));
a[s]=INF;
int h=0,tail=1;
d[1]=s;
while(h<tail){
h++;
int x=d[h];
for(int i=1;i<=n;i++)
if(f[x][i]&&!a[i])
{
pre[i]=x;
a[i]=min(a[x],f[x][i]);
d[++tail]=i;
}
}
if(!a[t]) break;
for(int i=t;i!=s;i=pre[i])
{
f[pre[i]][i]-=a[t];
f[i][pre[i]]+=a[t];
}
flow+=a[t];
}
return flow;
}
int main(){
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=1;i<=m;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
f[x][y]+=z;
}
int d=bfs(s,t);
printf("%d",d);
return 0;
} 2.Ford-Fulkerson算法
也就是深搜版
这里用的链表
位运算是为了找反向边
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int M=199999,INF=999999999;
int n,m,s,t,used[M];
int nex[M],head[M],cos[M],to[M],tot;
int add(int x,int y,int z){
cos[tot]=z;
nex[++tot]=head[x];
to[tot]=y;
head[x]=tot;
}
int dfs(int s,int t,int f){
if(s==t) return f;
for(int i=head[s];i;i=nex[i]){
int tmp=to[i];
if(cos[i-1]&&!used[tmp]){
used[tmp]=1;
int d=dfs(tmp,t,min(cos[i-1],f));
if(d>0){
cos[i-1]-=d;
cos[(i-1)^1]+=d;
return d;
}
}
}
}
int maxflow(int s,int t){
int flow=0;
while(1){
memset(used,0,sizeof(used));
int d=dfs(s,t,INF);
if(d==0)return flow;
flow+=d;
}
}
int main(){
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=1;i<=m;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,0);
}
int d=maxflow(s,t);
printf("%d",d);
return 0;
} 3.还有Dinic算法
就是综合以上两种方法，先用bfs建一个有层次的图，同一个层次的一定不是增广路，再用dfs找减少多余同层次的，就比较省事
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int M=199999,INF=999999999;
int n,m,s,t,used[M],deep[M];
int nex[M],head[M],cos[M],to[M],tot;
int add(int x,int y,int z){
cos[tot]=z;
nex[++tot]=head[x];
to[tot]=y;
head[x]=tot;
}
int bfs(int s,int t){
queue< int > d;
memset(deep,-1,sizeof(deep));
deep[s]=0;
d.push(s);
while(!d.empty()){
int x=d.front();
d.pop();
for(int i=head[x];i;i=nex[i]){
int tmp=to[i];
if(cos[i-1]&&deep[tmp]==-1){
deep[tmp]=deep[x]+1;
d.push(tmp);
}
}
}
return deep[t]!=-1;
}
int dfs(int s,int t,int f){
if(s==t) return f;
for(int i=head[s];i;i=nex[i]){
int tmp=to[i];
if(cos[i-1]&&deep[s]+1==deep[tmp]){
int d=dfs(tmp,t,min(cos[i-1],f));
if(d>0){
cos[i-1]-=d;
cos[(i-1)^1]+=d;
return d;
}
}
}
}
int maxflow(int s,int t){
int flow=0;
while(bfs(s,t)){
while(1)
{
int d=dfs(s,t,INF);
if(d==0)break;
flow+=d;
}
}
return flow;
}
int main(){
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=1;i<=m;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,0);
}
int d=maxflow(s,t);
printf("%d",d);
return 0;
}