概念
最大流: 在一个网络图上，每个边有流量限制，假如起始点有无线流量，求最多能有多少流量流到终点。
增广路: 一条从起始点到终点了路径，可以流流量。
算法
Ford-Fulkerson算法
解决这个问题，可以用Ford-Fulkerson算法。
该算法的核心就是寻找增广路。每找到一条增广路，就给它它能承受的最多流量。
我们注意到这样是有问题的，很可能最终结果不是最优的。因为先找到的增广路可能导致超过一条增广路断掉，最终答案劣。所以考虑反悔贪心。
反悔操作可以用反向边完成。建立反向边，每次增广路把正向边的流量给到反向边。这样一旦选到反向边，就相当于撤销了一次对边的选择操作，并把两次操作合并。可以证明这是最优的。
dfs爆搜即可。
Dinic算法
Dinic是针对FF的一种优化。
先使用bfs为所有点分层，然后每次dfs爆搜，只需要走层数较高的点，避免搜重和环。
弧优化
基于链式前向星，剪掉无用的dfs过程。分层后因为向回搜索不优，剪掉。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
#define int long long
using namespace std;
int tot=1,head[1000001],n,m,st,ed,dis[1000001],now[1000001];
struct node
{
int to,nex,w;
}e[1000001];
void add(int u,int v,int w)
{
e[++tot].to=v;
e[tot].w=w;
e[tot].nex=head[u];
head[u]=tot;
e[++tot].to=u;
e[tot].w=0;
e[tot].nex=head[v];
head[v]=tot;
}
bool bfs()
{
for(int i=1;i<=n;i++)
{
dis[i]=10000000000;
}
queue<int> q;
q.push(st);
dis[st]=0;
now[st]=head[st];
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].nex)
{
int v=e[i].to;
if(e[i].w>0&&dis[v]==10000000000)
{
q.push(v);
now[v]=head[v];
dis[v]=dis[u]+1;
if(v==ed) return true;
}
}
}
return false;
}
int dfs(int u,int sum)
{
if(u==ed) return sum;
int re=0,las;
for(int i=now[u];i&∑i=e[i].nex)
{
now[u]=i;
int v=e[i].to;
if(e[i].w>0&&dis[v]==dis[u]+1)
{
las=dfs(v,min(sum,e[i].w));
if(las==0) dis[v]=10000000000;
e[i].w-=las;
e[i^1].w+=las;
re+=las;
sum-=las;
}
}
return re;
}
signed main()
{
int ans=0;
scanf("%lld%lld%lld%lld",&n,&m,&st,&ed);
for(int i=1,u,v,w;i<=m;i++)
{
scanf("%lld%lld%lld",&u,&v,&w);
add(u,v,w);
}
while(bfs())
{
ans+=dfs(st,10000000000);
}
cout<<ans;
}