charleshe @ 2023-02-11 17:17:15
#include <iostream>
#include <queue>
#define int long long
using namespace std;
struct edge{
int v,w,nxt;
};
edge e[5005];
int h[202];
int cnt=1;
void add(int u,int v,int w){
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].nxt=h[u];
h[u]=cnt;
}
int n,m,s,t;
int lst[202];
int flw[202];
int flg[202][202];
bool bfs(){
for(int i=1;i<=n;i++) lst[i]=-1;
queue<int> q;
q.push(s);
flw[s]=1ll<<60;
while(!q.empty()){
int u=q.front();
q.pop();
if(u==t) break;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(w>0&&lst[v]==-1){
lst[v]=u;
flw[v]=min(flw[u],w);
q.push(v);
}
}
}
return lst[t]>-1;
}
int EK(){
int maxf=0;
while(bfs()){
maxf+=flw[t];
for(int i=t;i!=s;i=e[lst[i]^1].v){
// cout<<e[i].v<<" "<<e[i].w<<" "<<endl;
e[lst[i]].w-=flw[t];
e[lst[i]^1].w+=flw[t];
}
}
return maxf;
}
signed main(){
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
if(!flg[u][v]){
add(u,v,w);
add(v,u,0);
// cout<<u<<" "<<v<<" "<<w<<endl;
flg[u][v]=cnt;
}
else e[flg[u][v]-1].w+=w;
}
// for(int i=1;i<=n;i++){
// for(int j=h[i];j;j=e[j].nxt) cout<<i<<" "<<e[i].v<<" "<<e[j].w<<endl;
// }
cout<<EK()<<endl;
return 0;
}
写错了轻喷
差不多是照着这个写的
by ducati @ 2023-02-11 17:22:46
@charleshe 一共最多 edge
数组只开了
by charleshe @ 2023-02-11 17:24:10
@ducati 现在是全T力(悲
by ducati @ 2023-02-11 17:32:42
@charleshe 是的,但我看了一会儿也不知道为什么会全 T。感觉看不出什么问题 /kk
by charleshe @ 2023-02-11 17:38:29
艹,一处i打成了u导致的问题,已经过了
此贴完结