（该笔记用于复习，请不要用此学习）
最大流问题
对于输入的一个有向图，对于一条边(u,v,w)，我们建立一个图包含(u,v,w)和(v,u,0)
dinic算法的步骤：
1.对当前图进行bfs（只有边权>0的可以走），找到源点到每个点的最短路
2.判断源点是否可以走到汇点（bfs完直接判断即可）
可以->下一步
不可以->返回当前流量，结束
3.对图进行dfs，找到增广路
4.回到步骤1
模板
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int inf=1e9;
int n,m,s,t;
struct edge{
int v,w,nx;
}e[10005];
int cnt,hd[205],cur[205];
void add(int u,int v,int w){
e[++cnt]=edge{v,w,hd[u]};
hd[u]=cnt;
}
int dis[205];
bool bfs(){
queue<int> q;q.push(s);
memset(dis,0x3f,sizeof(dis));dis[s]=0;
for(int i=1;i<=n;i++)cur[i]=hd[i];
while(!q.empty()){
int u=q.front();q.pop();
for(int i=hd[u];i;i=e[i].nx){
int v=e[i].v;if(e[i].w<=0 || dis[v]<=dis[u]+1)continue;
dis[v]=dis[u]+1;
q.push(v);
}
}
return dis[t]!=0x3f3f3f3f;
}
inline int rev(int id){
if(id&1)return id+1;
else return id-1;
}
ll dfs(int u,int sum){
if(u==t)return sum;
ll res=0;
for(int i=cur[u];i;i=e[i].nx){
cur[u]=i;
int v=e[i].v;if(e[i].w<=0 || dis[v]!=dis[u]+1)continue;
int p=dfs(v,min(sum,e[i].w));
if(p==0)dis[v]=0x3b800001;
e[i].w-=p;e[rev(i)].w+=p;
res+=p;sum-=p;
}
return res;
}
ll dinic(){
ll res=0;
while(bfs())res+=dfs(s,inf);
return res;
}
int main(){
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=1;i<=m;i++){
int u,v,w;scanf("%d%d%d",&u,&v,&w);
add(u,v,w);add(v,u,0);
}
printf("%lld\n",dinic());
return 0;
}