WYXkk @ 2019-02-23 15:35:24
```cpp
#include<cstdio>
#include<iostream>
#include<fstream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
#define Set(a) memset(a,0,sizeof(a))
#define Set2(a) memset(a,0x3f,sizeof(a))
#define F(i,a,b) for(register int i=a,i##end=b;i<=i##end;++i)
#define UF(i,a,b) for(register int i=a,i##end=b;i>=i##end;--i)
#define openf(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
typedef long long LL;
typedef long long ll;
typedef unsigned long long ULL;
typedef unsigned long long ull;
template<typename T>void r(T& x)
{
x=0;T f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
x*=f;
return;
}
#define maxx(a,b) ((a)>(b)?(a):(b))
#define minn(a,b) ((a)<(b)?(a):(b))
const int inf=1<<30;
const int maxn=10000+5;
const int maxm=100000+5;
int n,m,s,t,top=1,maxflow;
int head[maxn],cur[maxn],dep[maxn],inque[maxn];
struct bian{
int v/*到达节点*/,flow/*流量*/,next/*下一条边的标号*/;
}node[2*maxm];
void add(int u,int v,int flow)
{
node[++top].v=v;
node[top].flow=flow;
node[top].next=head[u];
head[u]=top;
}
#include<queue>
bool bfs()
{
for(register int i=0;i<=n;i++) cur[i]=head[i],dep[i]=0x3f3f3f3f,inque[i]=0;
dep[s]=0;
queue<int> q;
int a;
q.push(s);
while(!q.empty())
{
a=q.front();
q.pop();
inque[a]=0;
for(int i=head[a];i!=0;i=node[i].next)
if(dep[node[i].v]>dep[a]+1&&node[i].flow!=0)
{
dep[node[i].v]=dep[a]+1;
if(!inque[node[i].v]) {q.push(node[i].v);inque[node[i].v]=1;}
}
}
return dep[t]!=0x3f3f3f3f;
}
int dfs(int u,int flow)
{
if(u==t)
{
maxflow+=flow;
return flow;
}
int rlow=0,used=0;
for(int i=cur[u];i!=0;i=node[i].next)
{
cur[u]=i;
if(dep[node[i].v]==dep[u]+1)
{
rlow=dfs(node[i].v,minn(flow-used,node[i].flow));
if(rlow!=0)
{
used+=rlow;
node[i].flow-=rlow;
node[i^1].flow+=rlow;
if(used==flow) break;
}
}
}
return used;
}
int dinic()
{
maxflow=0;
while(bfs()) dfs(s,inf);
return maxflow;
}
int main()
{
r(n);r(m);r(s);r(t);
int uu,vv,ww;
F(i,1,m)
{
r(uu);r(vv);r(ww);
add(uu,vv,ww);
add(vv,uu,0);
}
printf("%d\n",dinic());
return 0;
}
```