网络流（最大流）
基本概念
1.流网络，不考虑反向边
2.可行流，不考虑反向边
条件：1.容量限制 2.流量守恒
流量：从源点流出-流入源点
最大流：最大可行流
3.残留网络：考虑反向边，残留网络的可行流：f'+原图可行流=另一个可行流
4.增广路径
5.割：
1.定义：子集划分s属于S，t属于T
2.容量：S到T的容量之和，c(S,T)；最小割是最小的容量
3.流量：S到T的径流量
4.割的可行流f(s,v)一定小于等于c(S,T)
5.最大流最小割定理
1.流f是最大流
2.流f的残留网络中无增广路
3.存在某个割[S,T],使可行流流量等于割的容量EK
我们根据残留网的特性，如果没有增广网络那么就是最大流，我们可以去存储一下正反边，用
^1的形式去做这个路的方向变换，我们不断去判断是否存在增广路，用bfs的方法判断即可。O(nm^2)
#include<iostream>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 2e4+10;
int head[1<<10],n,m,S,T,cnt=0;
int q[1<<10],d[1<<10],pre[1<<10]; //q记录bfs,d记录最大容量,pre记录前驱
bool vis[1<<10];
struct node{
int next,to,f;
}edge[maxn];
void add(int a,int b,int c)
{
edge[cnt]=(node){head[a],b,c},head[a]=cnt++;
edge[cnt]=(node){head[b],a,0},head[b]=cnt++;
}
bool bfs()
{
memset(vis,false,sizeof(vis));
int hh=0,tt=0;
q[0]=S,vis[S]=true,d[S]=inf;
while(hh<=tt)
{
int t=q[hh++];
for(int i=head[t];~i;i=edge[i].next)
{
int ver=edge[i].to;
if(!vis[ver]&&edge[i].f)
{
vis[ver]=true;
d[ver]=min(d[t],edge[i].f);
pre[ver]=i;
if(ver==T) return true;
q[++tt]=ver;
}
}
}
return false;
}
int EK()
{
int res=0;
while(bfs())
{
res+=d[T];
for(int i=T;i!=S;i=edge[pre[i]^1].to)
edge[pre[i]].f-=d[T],edge[pre[i]^1].f+=d[T];
}
return res;
}
int main()
{
memset(head, -1, sizeof head);
scanf("%d%d%d%d", &n, &m, &S, &T);
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
printf("%d\n", EK());
return 0;
}Dinic
这个算法优化是进行分层图的优化加上当前弧优化，做一个bfs的遍历判断，然后直接dfs就直接把当前的流度完全流完。O（n^2m）。
#include<iostream>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
const int N=1e4+10,M=2e5+10;
int n,m,S,T;
int head[N],idx,q[N],d[N],cur[N];
struct Edge{
int next,to,f;
}edge[M];
void add(int a,int b,int c)
{
edge[idx]=(Edge){head[a],b,c},head[a]=idx++;
edge[idx]=(Edge){head[b],a,0},head[b]=idx++;
}
bool bfs()
{
/*
和EK不同点是这个是判断增广路和分层图，用d做层数的赋值，cur做一个当前弧优化
*/
int hh=0,tt=0;
memset(d,-1,sizeof d);
q[0]=S,d[S]=0,cur[S]=head[S];
while(hh<=tt)
{
int t=q[hh++];
for(int i=head[t];~i;i=edge[i].next)
{
int ver=edge[i].to;
if(d[ver]==-1&&edge[i].f)
{
d[ver]=d[t]+1;
cur[ver]=head[ver];
if(ver==T) return true;
q[++tt]=ver;
}
}
}
return false;
}
int find(int u,int limit)
{
if(u==T) return limit;
int flow=0;
for(int i=cur[u];~i&&flow<limit;i=edge[i].next)
{
//flow<limit是因为流出的量一定要大于0，如果为0就不用了
//一定要加不然会影响当前弧优化
cur[u]=i; //当前弧优化
int ver=edge[i].to;
if(d[ver]==d[u]+1&&edge[i].f)
{
int t=find(ver,min(edge[i].f,limit-flow));
if(!t) d[ver]=-1; //如果直接没有流量，就直接把这个点删除
edge[i].f-=t; edge[i^1].f+=t; flow+=t;
}
}
return flow;
}
int dinic()
{
int res=0,flow;
while(bfs())//返回是否有增广路并且分层图
while(flow=find(S,inf)) //在当前的分层图里的增广网络全部找出来
res+=flow;
return res;
}
int main()
{
memset(head,-1,sizeof head);
scanf("%d%d%d%d",&n,&m,&S,&T);
while(m--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
printf("%d\n",dinic());
return 0;
}
