学习网络流中。。。
目前的三个算法：
FF算法
大致步骤：
DFS不断寻找增广路径然后更新最大流
/********************************************
Ford-Fulkerson 算法
这玩意比较慢，洛谷上的模板题只能够跑过9个点
********************************************/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
#define MAX 10100
#define MAXL 210000
#define rg register
#define INF 1000000000
inline int read()
{
rg int x=0,t=1;rg char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-'){t=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*t;
}
int N,M,S,T,Ans=0;
bool vis[MAX];
struct Line
{
int v,next,w,fb;
}e[MAXL];
int h[MAX],cnt=1;
inline void Add(rg int u,rg int v,rg int w)
{
e[cnt]=(Line){v,h[u],w,cnt+1};
h[u]=cnt++;
e[cnt]=(Line){u,h[v],0,cnt-1};//存反边
h[v]=cnt++;
}
int DFS(rg int u,rg int t,rg int f)//从u到t，当前流量f
{
if(u==t||f==0)return f;//到达终点或者已经无法增广了
vis[u]=true;//标记为访问过
for(int i=h[u];i;i=e[i].next)//访问所有边
{
rg int v=e[i].v,d;
if(!vis[v]&&e[i].w>0&&(d=DFS(v,t,min(e[i].w,f))))
//如果v未访问并且这条边的流量>0并且
//当前寻找出来的可以更新的流量不为0
{
e[i].w-=d;//更新流量
e[e[i].fb].w+=d;//反边
return d; //返回当前的最大流量
}
}
return 0;
}
int main()
{
N=read();M=read();S=read();T=read();
for(rg int i=1;i<=M;++i)
{
rg int u=read(),v=read(),w=read();
Add(u,v,w);
}
rg int Ans=0;
while(1)//不断寻找增广路径
{
for(rg int i=1;i<=N;++i)vis[i]=false;
rg int f=DFS(S,T,INF);//找增广路径
if(!f)break;
Ans+=f;
}
printf("%d
",Ans);
return 0;
}
EK算法
大致步骤：
和FF算法的思想是一样的，但是使用BFS来寻找增广路径，效率比FF更高
/********************************************
EK算法
比FF算法快多了，利用BFS寻找增广路
可以解决Dinic解决不了的图（不能够分层的图）
********************************************/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
#define MAX 10100
#define MAXL 210000
#define rg register
#define INF 1000000000
inline int read()
{
rg int x=0,t=1;rg char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-'){t=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*t;
}
int N,M,S,T,Ans=0;
int a[MAX];
queue<int> Q;
int pre[MAXL];
struct Line
{
int u,v,next,w,c,fb;//w是流量，c是容量
}e[MAXL];
int h[MAX],cnt=1;
inline void Add(rg int u,rg int v,rg int w)
{
e[cnt]=(Line){u,v,h[u],0,w,cnt+1};
h[u]=cnt++;
e[cnt]=(Line){v,u,h[v],0,0,cnt-1};//存反边
h[v]=cnt++;
}
int main()
{
N=read();M=read();S=read();T=read();
for(rg int i=1;i<=M;++i)
{
rg int u=read(),v=read(),w=read();
Add(u,v,w);
}
rg int Ans=0;
while(1)//不断寻找增广路径
{
for(rg int i=1;i<=N;++i)a[i]=0;
while(!Q.empty())Q.pop();
Q.push(S);
pre[S]=0;
a[S]=INF;
while(!Q.empty())
{
int u=Q.front();Q.pop();
for(int i=h[u];i;i=e[i].next)
{
int v=e[i].v;
if(!a[v]&&e[i].c>e[i].w)//可以增广
{
a[v]=min(a[u],e[i].c-e[i].w);//求最小的流量
pre[v]=i;//储存增广路径
Q.push(v);
}
}
if(a[T])break;//增广到了终点
}
if(!a[T])break;//未增广
for(int u=T;u!=S;u=e[pre[u]].u)//增加流量
{
e[pre[u]].w+=a[T];
e[e[pre[u]].fb].w-=a[T];
}
Ans+=a[T];
}
printf("%d
",Ans);
return 0;
}
Dinic
这是目前，我学的最优的一个最大流算法(我太弱了！！！)
大致步骤：
先用BFS对图进行分层
再用DFS寻找增广路径
Dinic是FF的升级版？（我是这么觉得的。。。）
效率高很多
但是有些图不能够分层。。。。所以。。。。。
学习一下EK还是比较重要的
/********************************
Dinic算法
对于可以分层的图而言
效率比EK和FF高很多
********************************/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
#define MAX 10100
#define MAXL 210000
#define rg register
#define INF 1000000000
inline int read()
{
rg int x=0,t=1;rg char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-'){t=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*t;
}
int N,M,S,T,Ans=0;
bool vis[MAX];
struct Line
{
int v,next,w,fb;
}e[MAXL];
int h[MAX],cnt=1;
int level[MAX];
inline void Add(rg int u,rg int v,rg int w)
{
e[cnt]=(Line){v,h[u],w,cnt+1};
h[u]=cnt++;
e[cnt]=(Line){u,h[v],0,cnt-1};//存反边
h[v]=cnt++;
}
inline bool BFS()//分层
{
for(int i=1;i<=N;++i)level[i]=0;
level[S]=1;
queue<int> Q;
while(!Q.empty())Q.pop();
Q.push(S);
while(!Q.empty())
{
int u=Q.front();Q.pop();
for(int i=h[u];i;i=e[i].next)
{
int v=e[i].v;
if(e[i].w&&!level[v])//可以增广
{
level[v]=level[u]+1;
Q.push(v);
}
}
}
return level[T];//返回是否存在增广路
}
int DFS(rg int u,rg int t,rg int f)//从u到t，当前流量f
{
if(u==t||f==0)return f;//到达终点或者已经无法增广了
int re=0;//返回值
for(int i=h[u];i;i=e[i].next)//访问所有边
{
rg int v=e[i].v,d;
if(e[i].w&&level[v]==level[u]+1)//可以增广，并且满足分层图的要求
{
d=DFS(v,T,min(f,e[i].w));
re+=d;
f-=d;
e[i].w-=d;//更新流量
e[e[i].fb].w+=d;//反边
}
}
return re;
}
inline int Dinic()
{
int re=0;
while(BFS())re+=DFS(S,T,INF);
return re;
}
int main()
{
N=read();M=read();S=read();T=read();
for(rg int i=1;i<=M;++i)
{
rg int u=read(),v=read(),w=read();
Add(u,v,w);
}
rg int Ans=Dinic();
printf("%d
",Ans);
return 0;
}