基本概念
网络流，即网络+流
网络就是由许多结点和边组成的图，在这里边权表示允许通过的最大流量
在网络中，有两个特殊的结点，一个叫源点，一个叫汇点
网络流中最大流问题可以看成是：假设在源点注入无限多的水流，最终会流到汇点的最大流量（中间有点类似木桶原理，一条完整路径上的最大流量是最小的边权。
最小割概念：在网络中选取若干条边删除，使得源点到汇点变成不连通的，而且删掉的边权之和最小。
定理：最大流在数值上等于最小割。
算法
如果直接找从源点到汇点的一条路径，可能经过了边权不那么优的边
引入反向弧——每次选取 i 到 j 的一条路径中 k 的流量，给它的反向边边权赋予权值 k。
实际的意义是可以反悔。如果某条边被正反走了两次，那么可以认为这条边是没有选取的
EK算法
最基础的、不加优化的网络流算法。
时间复杂度 \(O(v*e^2)\)
每次都从 S 到 T 寻找增广路，如果找到，把答案加进 ans
直到找不到了退出
点击查看代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int inf = 1e9; //可能的最大流量
const int N = 205;
int n,m;
ll g[N][N],pre[N];
int S,T;
ll bfs(int s,int t){ // 求s到t的一条路的流量
ll flow[N]={0};
memset(pre,-1,sizeof(pre));
flow[s] = inf;
pre[s] = 0;
queue<int>q;
q.push(s);
while(!q.empty()){
int u = q.front();
q.pop();
for(int i=1;i<=n;i++){
if(i!=s&&g[u][i]>0&&pre[i]==-1){
pre[i] = u;
q.push(i);
flow[i]=min(flow[u],g[u][i]);
}
}
}
if(pre[t]==-1) return -1;
return flow[t];
}
ll maxflow(int s,int t){
ll Maxflow = 0;
while(1){
ll flow = bfs(s,t);
if(flow==-1) break;
int cur = t;
while(cur!=s){ //增加反向弧
int father = pre[cur];
g[father][cur] -= flow;
g[cur][father] += flow;
cur = father;
}
Maxflow += flow;
}
return Maxflow;
}
int main(){
int t;
// cin>>t;
t=1;
int cnt=0;
while(t--){ // ind 1 to n m dugs
scanf("%d%d",&n,&m);
scanf("%d%d",&S,&T); //源点、汇点
memset(g,0,sizeof(g));
ll w;
for(int i=1,u,v;i<=m;i++){
scanf("%d%d%lld",&u,&v,&w);
g[u][v]+=w;
}
// printf("Case %d: ",++cnt);
printf("%lld\n",maxflow(S,T));
}
return 0;
}
ISAP算法
时间复杂度很低的优秀算法。
点击查看代码
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
#define ll long long
using namespace std;
#define inf 0x3f3f3f3f
const int maxn = 409;
ll pre[maxn],gap[maxn],h[maxn];//pre记录是从哪一条边到达i的，gap记录在i层中有几个点，h记录i点的层次。
ll firs[maxn];//邻接表建边
struct node{
ll v,flow,nex;
}edge[maxn*maxn];
int N, n, m, S, T;
inline int in(int x) {
return x;
}
inline int out(int x) {
return x + n + 1;
}
void build_edge(int u,int v,int flow){
edge[N]=(node){v,flow,firs[u]};
firs[u]=N++;
edge[N]=(node){u,0,firs[v]};
firs[v]=N++;
}
void bfs(int s,int t)//广搜建层，不过这里是从汇点开始的，别弄错了，
{
//初始化
memset(h,-1,sizeof(h));
memset(gap,0,sizeof(gap));
queue<int>q;
while(!q.empty())q.pop();
q.push(t);
h[t]=0;//将汇点定义为0层
gap[0]=1;//0层点的个数加一
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=firs[u];i!=-1;i=edge[i].nex)
{
int v=edge[i].v;
if(h[v]==-1)
{
h[v]=h[u]+1;
gap[h[v]]++;//记录当前层的个数
q.push(v);
}
}
}
}
ll isap(int s,int t,int n){
bfs(s,t);
memset(pre,0,sizeof(pre));//记录该点的前驱是谁（这里的前驱是指边，不是点）
ll ans=0,d,u=s;//ans记录最大流,d记录当前路径中的最小流,u记录当前查找到哪个点了。
while(h[s]<n)//如果源点的层小于点的个数就可能还有流
{
int flag=1;//判断是否能够走，能否找到流。
if(u==s) d=inf;//如果再次从源点出发，就初始化d，
for(int i=firs[u];i!=-1;i=edge[i].nex)
{
ll v=edge[i].v,flow=edge[i].flow;
if(h[v]+1==h[u]&&flow)
{
pre[v]=i;//记录该点是由哪条边到达的
u=v;//记录要去哪个点
d=min(d,flow);//记录最小流
flag=0;//能够往前走
if(v==t)//如果走到了汇点
{
while(u!=s)//原路返回，更新边的容量，与dinic的dfs思路一样
{
int j=pre[u];
edge[j].flow-=d;
edge[j^1].flow+=d;
u=edge[j^1].v;
}
ans+=d;//加上当前找到的流
}
break;
}
}
if(flag)//如果没有找到下面的路,就更新点的层次
{
if(--gap[h[u]]==0) //如果该层上没有了点，说明没法继续查找了，结束。
break;
ll min_=n-1;
for(int i=firs[u];i!=-1;i=edge[i].nex)//查找与u相连的最小层，
{
ll v=edge[i].v,flow=edge[i].flow;
if(flow)
min_=min(min_,h[v]);
}
h[u]=min_+1;//重新给u建层
gap[h[u]]++;//更新层的个数
if(u!=s)//重要一步，如果当前点不是源点就要向后退一步，继续查找。
u=edge[pre[u]^1].v;
}
}
return ans;
}
int main(){
int t; scanf("%d", &t);
while(t--) {
scanf("%d%d",&n,&m);
memset(firs,-1,sizeof(firs));
N=0;
for(int i=1,u,v;i<=m;i++){
scanf("%d%d",&u,&v);
build_edge(out(u), in(v), 1);
}
for(int i = 0; i <= n; i++) {
build_edge(in(i), out(i), 1);
}
S = out(0);
T = in(n);
n = n * 2 + 2;
printf("%lld\n",isap(S,T,n));
}
return 0;
}