AdGats @ 2021-08-11 08:59:33
#include<bits/stdc++.h>
using namespace std;
const int N=205,M=5e3+5;
const long long INF=1e16+5;
long long d[N],delta,ans;
int n,m,s,t,k,head[N],cur[N];
queue<int>q;
struct node{
int v,next;
long long w;
}edge[M];
inline void addedge(int from,int to,int w){
edge[++k].next=head[from];
edge[k].v=to;
edge[k].w=w;
head[from]=k;
}
inline int bfs(){
while(!q.empty()) q.pop();
memset(d,0,sizeof(d));
d[s]=1;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];~i;i=edge[i].next){
int v=edge[i].v,w=edge[i].w;
if(d[v]) continue;
if(w) d[v]=d[u]+1,q.push(v);
}
}
return d[t];
}
inline long long dfs(int u,long long flow){
if(u==t) return flow;
long long res=0;
for(int& i=cur[u];~i&&flow;i=edge[i].next){
long long v=edge[i].v,&w=edge[i].w;
if(d[v]==d[u]+1&&w){
long long de=dfs(v,min(flow,w));
if(de) w-=de,edge[i^1].w+=de,res+=de,flow-=de;
else d[v]=INF;
}
}
if(!res) d[u]=0;
return res;
}
inline void dinic(){
while(bfs()){
for(int i=1;i<=n;i++) cur[i]=head[i];
while(delta=dfs(s,INF)) ans+=delta;
}
}
int main(){
memset(head,-1,sizeof(head));
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
addedge(x,y,z);
addedge(y,x,0);
}
dinic();
cout<<ans<<"\n";
return 0;
}
by _l_l_l_l_l_ @ 2021-08-11 09:16:08
@_B_TC 这题要
by AdGats @ 2021-08-11 09:28:47
@WenZKbb 有WA应该不是O2的问题
by Nt_Tsumiki @ 2021-10-08 20:44:30
@_B_TC k要赋值成1