Dinic/ISAP求最大流

算法执行过程见蓝书和OI-wiki，当前弧优化见OI-wiki的描述，代码见下

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=10010,M=100010,inf=1<<29;
int now[N],End[M<<1],Next[M<<1],Len[M<<1],Last[N];
int n,m,s,t,cnt=1,d[N];
ll maxflow=0;
queue<int> q;
void add(int x,int y,int z)
{
	End[++cnt]=y,Next[cnt]=Last[x],Len[cnt]=z,Last[x]=cnt;
	End[++cnt]=x,Next[cnt]=Last[y],Len[cnt]=0,Last[y]=cnt;
}
bool bfs()//构建分层图
{
	while(!q.empty()) q.pop();
	memset(d,0,sizeof(d));//d表示层次
	q.push(s),d[s]=1;
	now[s]=Last[s];//now是当前弧优化
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(int i=Last[x];i;i=Next[i])
		{
			int y=End[i];
			if(!Len[i]||d[y]) continue;
			q.push(y),d[y]=d[x]+1;
			now[y]=Last[y];//构建分层图的时候，初始化当前弧
			if(y==t) return 1;
		}
	}
	return 0;
}
int dinic(int x,int flow)//dinic(x,flow)表示有flow流量流进x，最多有多少流量可以从x流出到t
{
	if(x==t) return flow;
	int rest=flow,k,i;//rest表示还没有分配的剩余的流量
	for(i=now[x];i&&rest;i=Next[i])
	if(Len[i]&&d[End[i]]==d[x]+1)//如果是分层图上面的边
	{   
	    now[x]=i;
	    //当前弧优化
	    //对于上一条分层图的边
	    //如果我们分配的流量是rest（也就是说rest<len）
	    //那么就说明我们分配小于rest的流量就可以让上一条边堵塞（因为rest为0的话就会结束循环）
	    //所以接下来就都不用考虑上一条边了，因为一定已经堵塞了
	    //如果我们分配的流量是len（也就是说rest>len）
	    //那么无论len是否被用完，都可以说明上一条边堵塞了，也不用考虑了
	    //如果将当前弧优化放在`return flow-rest`的上面一句
	    //那么当前这个分层图一定只会dfs到x这个点一次
	    //就会导致外面构建分层图的bfs执行更多次
	    //于是TLE
	    //所以当前弧优化要放在这个位置
		k=dinic(End[i],min(rest,Len[i]));
		if(!k) d[End[i]]=0;//如果一点流量都流不出去，直接删除这条边
		Len[i]-=k;
		Len[i^1]+=k;//更新残存网络
		rest-=k;
	}
	return flow-rest;
}
int main()
{
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(int i=1;i<=m;i++)
	{
		int u,v,c;
		scanf("%d%d%d",&u,&v,&c);
		add(u,v,c);
	}
	int flow;
	while(bfs()) 
	while(flow=dinic(s,inf))//其实这个while可以改成if，因为初始流量为无穷，走一遍就可以把每条以s为起点的边流堵塞；也就是说这个while只会执行一次
	maxflow+=flow;
	printf("%lld",maxflow);
    return 0;
}