```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#define ll long long
using namespace std;
ll re(){
ll x=0;int f=1;char t=getchar();
while(t<'0'||t>'9'){if(t=='-')f=-1;t=getchar();}
while(t>='0'&&t<='9')x=x*10+t-'0',t=getchar();
return x*f;
}
const int N=210,M=10010;
int n,m,s,t;
int fir[N],poi[M],net[M],sumb=1;
ll val[M];
void add(int a,int b,int c){
net[++sumb]=fir[a];
poi[sumb]=b;
val[sumb]=c;
fir[a]=sumb;
}
int vis[N];
ll ans=0;
int l[N],head,tail;
int la_e[N],dep[N];
int bfs(){
for(int i=1;i<=n;i++){
vis[i]=0;
la_e[i]=fir[i];
dep[i]=1e9;
}
int pdt=0;
dep[s]=0;
head=0,tail=1;
l[1]=s;
while(head<tail){
int now=l[++head];
vis[now]=0;
for(int i=fir[now];i;i=net[i]){
int p=poi[i];
if(dep[p]==1e9&&val[i]){
dep[p]=dep[now]+1;
if(p==t){
return 1;
}
// {pdt=1;continue;}
if(vis[p])continue;
l[++tail]=p;
vis[p]=1;
}
}
}
return pdt;
}
ll dfs(int x,ll flow){
if(x==t){
ans+=flow;
return flow;
}
ll used=0;
for(int i=la_e[x];i&&flow;i=net[i]){
la_e[x]=i;//当前弧优化
int p=poi[i];
if(dep[p]==dep[x]+1&&val[i]){
ll nf=0;
if(nf=dfs(p,min(flow-used,val[i]))){
val[i]-=nf;
val[i^1]+=nf;
used+=nf;
if(used==nf)return used;
}
}
}
return used;
}
void dinic(){
while(bfs()){
dfs(s,1e9);
}
return;
}
int main(){
n=re(),m=re(),s=re(),t=re();
for(int i=1;i<=m;i++){
int x1=re(),x2=re(),x3=re();
add(x1,x2,x3);
add(x2,x1,0);
}
dinic();
printf("%lld\n",ans);
return 0;
}
```
by yangshiyu10 @ 2022-08-11 09:01:05
要加点其他的剪枝
by 方123456 @ 2022-08-11 09:04:43
加了点小剪枝，压下去了！
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#define ll long long
using namespace std;
ll re(){
ll x=0;int f=1;char t=getchar();
while(t<'0'||t>'9'){if(t=='-')f=-1;t=getchar();}
while(t>='0'&&t<='9')x=x*10+t-'0',t=getchar();
return x*f;
}
const int N=210,M=10010;
int n,m,s,t;
int fir[N],poi[M],net[M],sumb=1;
ll val[M];
void add(int a,int b,int c){
net[++sumb]=fir[a];
poi[sumb]=b;
val[sumb]=c;
fir[a]=sumb;
}
int vis[N];
ll ans=0;
int l[N],head,tail;
int la_e[N],dep[N];
int bfs(){
for(int i=1;i<=n;i++){
vis[i]=0;
la_e[i]=fir[i];
dep[i]=1e9;
}
int pdt=0;
dep[s]=0;
head=0,tail=1;
l[1]=s;
while(head<tail){
int now=l[++head];
vis[now]=0;
for(int i=fir[now];i;i=net[i]){
int p=poi[i];
if(dep[p]==1e9&&val[i]){
dep[p]=dep[now]+1;
if(p==t){
return 1;
}
// {pdt=1;continue;}
if(vis[p])continue;
l[++tail]=p;
vis[p]=1;
}
}
}
return pdt;
}
ll dfs(int x,ll flow){
if(x==t){
ans+=flow;
return flow;
}
if (flow==0) return 0;
ll used=0;
for(int i=la_e[x];i&&flow;i=net[i]){
la_e[x]=i;//当前弧优化
int p=poi[i];
if(dep[p]==dep[x]+1&&val[i]){
ll nf=0;
if(nf=dfs(p,min(flow-used,val[i]))){
val[i]-=nf;
val[i^1]+=nf;
used+=nf;
flow-=nf;
if (flow==0) break;
// if(used==nf)return used;
}
else dep[p]=1e9;
}
}
return used;
}
void dinic(){
while(bfs()){
dfs(s,1e9);
}
return;
}
int main(){
n=re(),m=re(),s=re(),t=re();
for(int i=1;i<=m;i++){
int x1=re(),x2=re(),x3=re();
add(x1,x2,x3);
add(x2,x1,0);
}
dinic();
printf("%lld\n",ans);
return 0;
}
```
by 方123456 @ 2022-08-11 09:10:09
@[yangshiyu10](/user/413006)
by 方123456 @ 2022-08-11 09:10:40
@[方123456](/user/128754)
谢谢大佬，找到慢的地方了
by yangshiyu10 @ 2022-08-11 09:39:14