- 源：只出不进，叫做源点。
- 汇点：只进不出，叫做汇点。
- 每条边可以通过的最大量称作容量
- 每条边实际通过的量称作流量
- 每条边容量-流量称作残量 (表示这条边距最大承受的量的数量)
- 一条完整的路距最大的承受量取决于这条路中的最小流量(木桶效应)
最大流
定义
- 给定指定的一个有向图,其中有两个特殊的点源
和汇
,每条边有指定的容量
,求满足条件的从
到
的最大流
).
通俗点来讲就是：
你家是汇，自来水厂是源，然后自来水厂和你家之间修了很多条水管子接在一起，水管子规格不一，有的容量大，有的容量小，然后问自来水厂开闸放水，你家收到水的最大流量是多少。
假如在自来水厂可以非常满的灌满每一条水管，但是由于水管的容量不一样所以能通到家中的最大流量肯定不是水管容量的总和。那么最大流是多少呢？
如图
其中号是源点，
是汇点。每条边的容量都是
我们可以一眼看出图中的1到4的最大流是2，通过路径(1,2,4)(1,3,4),最大流为
然后对于程序，我们先引入一个叫做残量图的概念:
顾名思义，残嘛，就是剩的意思，即剩下的量，我们把一条边的最大容量和其实际的流量
的差值叫做残量,即
残量=
然后我们将残量作为每一条边的权值，构建一个图就叫做残量图，若权值为，那么就相当于一条断边
此时，假设我们从源出发进行的某一次到了汇，那么就说明这条路线的流量还可以增加，具体增加的量就被这条路线上的流量最小的那条边决定了，我们把这样的路叫做增广路
(增广路就是一条从源点到汇点的路，并且带有一个值，表示该增广路的最大流量，该值得大小取决于该增广路中拥有最小流量的边。)
就像上图，我们知道这条路线是可以在增大流量的，且最大可增大的流量是
得到了这个图的残量图
然后我们再
但是并不是这样的啊？？
这个时候我们发现，如果程序在的时候若可以向
的话就不会出错了啊！那么这个时候，如果我们给这个图上的每一个点都标上深度的话，我们
算法的思想就出来了，就是不断用
标深度然后不断
但是仅仅通过标记深度能不能完全解决问题呢？答案是不能的，即使它可以大幅度减少那如果说我们可以让程序在dfs到3的时候发现问题并后悔不就ok了吗？
于是有一种最easy的方法就是引入一个反向边的概念，即每一条边（u,v）都有一条反向边(v,u),且这两条边的最大容量相等，一对边的实际流量之和等于最大流量(容量)，即
假如一条边的流量时,反向边就
.
于是就有
然后根据
然后我们继续dfs，把反向边也当作可走的边
然后图就成了这样
最大流为
仔细观察可以发现，上图其实和我们直接和
得到的结果一样！！这也就正确了！
其实奥妙在第2个
当程序将边的流量加一，
的流量减一时，其实就相当于把边
，于是就有了两条路
和
这就是其奥妙所在
于是这个算法框架就此浮出水面：
先标深度再用直到
Dinic算法
就是应用外，还需要传入一个表示“目前为止所有边的最小残量”的
,当前节点
时终止
.以免重复计算遍历过的子边.
cur数组原理是什么呢？其实就是当我们在对一个节点u（假设有
儿子）进行增广时，把他的儿子
的可用流量都用完了，那么在下一次
时，我们如果可以直接从儿子
开始进行增广就可以大大减少额外的时间开销
cur数组实现:我们可以在
数组，在
数组拷贝到
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int M=2*100000+10;
int head[M],cnt=0;
int dis[M],cur[M];
int n,m,s,t;
struct node
{
int v,w,nxt;
} edge[M];
void add(int x,int y,int w)
{
edge[cnt].nxt=head[x];//边的编号一定要从0开始，因为0^1=1,1^1=0;2^1=3,3^1=2
edge[cnt].v=y;
edge[cnt].w=w;
head[x]=cnt;
cnt++;
}
void dataset( )
{
memset(head,-1,sizeof(head));
scanf("%d%d%d%d",&n,&m,&s,&t);
int a,b,c;
for(int i=1; i<=m; i++)
{
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);//正向边初始值为容量
add(b,a,0);//反向边初始值为0
}
}
bool bfs(int s)
{
memset(dis,-1,sizeof(dis));
dis[s]=0;
queue<int>qu;
qu.push(s);
while(!qu.empty( ))
{
int u=qu.front( );
qu.pop( );
for(int i=head[u]; i!=-1; i=edge[i].nxt)
{
int v=edge[i].v;
if(dis[v]==-1&&edge[i].w)
{
dis[v]=dis[u]+1;
qu.push(v);
}
}
}
return dis[t]!=-1;
}
int dfs(int u,int flo)
{
if(u==t)
{
return flo;
}
int detla=flo;
for(int i=cur[u]; i!=-1; i=edge[i].nxt)
{
cur[u]=edge[i].nxt;
int v=edge[i].v;
if(dis[v]==dis[u]+1&&edge[i].w>0)
{
int d=dfs(v,min(detla,edge[i].w));
edge[i].w-=d;
edge[i^1].w+=d;//反向边
detla-=d;
if(detla==0)
{
break;
}
}
}
return flo-detla;
}
int dini( )
{
int ans=0;
while(bfs(s))
{
for(int i=1; i<=n; i++)
{
cur[i]=head[i];
}
ans+=dfs(s,INF);
}
return ans;
}
int main( )
{
dataset( );
printf("%d\n",dini( ));
return 0;
}
本文参考博客
https://blog.csdn.net/weixin_43907802/article/details/84705855
