最大流

一些定义

网络
1.网络是一个有向图。
2.对于每条在图中的边 \((u,v)\) 都有一个权值 \(c(u,v)\) ，称为容量。对于每条不在图中的边 \((u,v)\) ，记 \(c(u,v)=0\) 。
3.有两个特殊的点：源点，记作 \(s\) ，汇点，记作 \(t\) 。
流
定义在网络 \(G\) 上的流函数 \(f(u,v)\) 表示流经 \((u,v)\) 这条边的流量，则有以下的性质：
1.\(f(u,v) \leq c(u,v)\) 。
2.\(f(u,v)+f(v,u)=0\) 。
3.从源点流出的流量与流入汇点的流量相等。
残量网络
记 \(c_f(u,v)\) 为边 \((u,v)\) 的剩余流量，其值为 \(c(u,v)-f(u,v)\) 。
定义网络 \(G\) 的残量网络为网络 \(G\) 中所有节点和剩余流量大于 \(0\) 的边构成的子图。
注意：剩余流量大于 \(0\) 的边可能并不在原图中
增广路
在残量网络中，一条从源点到汇点的路径即为增广路。
最大流
给定一个网络，求源点流向汇点的最大的流量。（可能有很多条路）

EK算法

bfs 找出从源点到汇点的每一条增广路然后对其进行增广。
增广时将该路径上的每条边的剩余流量的最小值（即能流过的最大流量）累加进答案，再把每条边及其反向边的剩余流量更新。
由于可能要反悔，所以建边时把每条边的反向边也建上。这样反着跑回去就可以恢复边的剩余流量。
时间复杂度为 \(O(nm^2)\) 。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#define int long long
using namespace std;
const int N=210;
const int inf=1e18;
int n,m,s,t,ans;
int vis[N],pre[N],dis[N][N],mn[N];
vector <int> e[N];
queue <int> q;
int MIN(int x,int y)
{
	return x<y?x:y;
}
bool bfs()
{
	memset(vis,0,sizeof(vis));
	while(q.size()) q.pop();
	vis[s]=1,mn[s]=inf,q.push(s);
	while(q.size())
	{
		int x=q.front();q.pop();
		for(int i=0;i<e[x].size();i++)
		{
			int to=e[x][i];
			if(vis[to]) continue;
			if(dis[x][to]>0)
			{
				mn[to]=MIN(mn[x],dis[x][to]);
				pre[to]=x,q.push(to),vis[to]=1;
				if(to==t) return true;
			}
		}
	}
	return false;
}
void upd()
{
	int x=t;
	while(x!=s)
	{
		dis[x][pre[x]]+=mn[t];
		dis[pre[x]][x]-=mn[t];
		x=pre[x];
	}
	ans+=mn[t];
}
signed main()
{
	scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		scanf("%lld%lld%lld",&x,&y,&z);
		e[x].push_back(y);
		dis[x][y]+=z;
		e[y].push_back(x);
	}
	while(bfs()) upd();
	printf("%lld",ans);
	return 0;
}

dinic算法

建好反向边后对图进行分层（即令每条边的边权为 \(1\) ，bfs 跑源点到每个点的最短路）。
这样分层后，设分层得到的数组为 \(d\) ，则最短增广路上的每一条边 \((u,v)\) 一定满足 \(d_u+1=d_v\) 。所以，只要找满足该条件的增广路即可。
这样，可以免去一些不必要的重复查找。
时间复杂度 \(O(n^2m)\) 。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#define int long long
using namespace std;
const int N=210;
const int inf=1e18;
int n,m,s,t,ans,d[N];
int dis[N][N];
vector <int> e[N];
queue <int> q;
int MIN(int x,int y)
{
	return x<y?x:y;
}
bool bfs()
{
	memset(d,0,sizeof(d));
	while(q.size()) q.pop();
	d[s]=1,q.push(s);
	while(q.size())
	{
		int x=q.front();q.pop();
		for(int i=0;i<e[x].size();i++)
		{
			int to=e[x][i];
			if(d[to]||dis[x][to]<=0) continue;
			d[to]=d[x]+1,q.push(to);
			if(to==t) return true;
		}
	}
	return false;
}
int dfs(int x,int mn)
{
	if(x==t) return mn;
	int sum=0;
	for(int i=0;i<e[x].size();i++)
	{
		int to=e[x][i];
		if(dis[x][to]<=0||d[to]!=d[x]+1) continue;
		int res=dfs(to,MIN(mn,dis[x][to]));
		dis[x][to]-=res,dis[to][x]+=res;
		mn-=res,sum+=res;
	}
	if(!sum) d[x]=0;
	return sum;
}
signed main()
{
	scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		scanf("%lld%lld%lld",&x,&y,&z);
		e[x].push_back(y);
		dis[x][y]+=z;
		e[y].push_back(x);
	}
	while(bfs()) ans+=dfs(s,inf);
	printf("%lld",ans);
	return 0;
}

最大流

原文：https://www.cnblogs.com/zhs1/p/14382601.html