不知道为啥wa了3个点,用dinic啥优化都没加
评测:
https://www.luogu.com.cn/record/100582781
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxx 200000000000000000LL
struct point{
ll x,step;
};
ll n,m,s,t;
ll g[205][205],cen[205],cnt[205];
ll ans=0;
point q[1040005];
bool bfs(){
memset(cen,-1,sizeof(cen));
q[1].x=s,q[1].step=1;
ll f=1,e=1;
while(f<=e){
point u=q[f];
f++;
if(cen[u.x]!=-1)continue;
cen[u.x]=u.step;
for(ll i=1;i<=n;i++){
if(g[u.x][i]>0&&cen[i]==-1){
e++;
q[e].x=i,q[e].step=u.step+1;
}
}
}
if(cen[t]==-1)return 0;
return 1;
}
ll dfs(ll now,ll val){
if(now==t)return val;
for(ll i=1;i<=n;i++){
if(g[now][i]>0&&cen[i]==cen[now]+1){
ll jia=dfs(i,min(val,g[now][i]));
if(jia>0){
g[now][i]-=jia;
g[i][now]+=jia;
return jia;
}
}
}
return 0;
}
void dinic(){
while(1){
bool flag=bfs();
if(flag==0)break;
while(1){
ll jia=dfs(s,maxx);
ans+=jia;
if(jia==0)break;
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m>>s>>t;
memset(g,0,sizeof(g));
for(ll i=1;i<=m;i++){
ll xx,yy,vv;
cin>>xx>>yy>>vv;
g[xx][yy]=vv;
}
dinic();
cout<<ans<<"\n";
return 0;
}