ynxynx @ 2022-05-28 21:50:38
//64pt
#include<bits/stdc++.h>
using namespace std;
const int N=10000001;
int n,m,head[N],cnt=1,rad[N],f[N],s,t,vip[N];
struct node{
int to,nxt,w;
}tr[N];
void add(int u,int v,int w){
tr[++cnt].to=v;
tr[cnt].w=w;
tr[cnt].nxt=head[u];
head[u]=cnt;
}
queue<int> que;
bool bfs() {//分层
for(int i=0;i<=n;i++) f[i]=0;
que.push(s);
f[s]=1;
while (!que.empty()) {
int now=que.front();
que.pop();
for (int i=head[now];i;i=tr[i].nxt) {
int v=tr[i].to;
if (f[v] || tr[i].w<=0) continue;//???
f[v]=f[now]+1;//分层
que.push(v);
// if(v==t) return 1;
}
}
return f[t]!=0;
}
int dfs(int now,int a) {
if (now==t) {
return a;
}
int tmp=a;//流过这段的流量
for (int i=head[now];i;i=tr[i].nxt) {
int v=tr[i].to;
if (f[v]==f[now]+1 && tr[i].w>=0) {//可以走
int k=min(tmp,tr[i].w);//流
int dlt=dfs(v,k);//最小
// dlt=min(dlt,tmp);
tr[i].w-=dlt;
tr[i^1].w+=dlt;//残量
tmp-=dlt;
if (tmp<=0) break;// 0
}
}
return a-tmp;
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>m>>s>>t;
for (int i=1;i<=m;i++) {
int u,v,w;
cin>>u>>v>>w;
add(u,v,w);
add(v,u,0);//反边
}
int ans=0,dlt=114514;
while (bfs()) {
ans+=dfs(s,1e9);//增广
}
cout<<ans;
return 0;
}
/*
5 6 1 5
1 5 1
2 5 1
1 2 99
2 3 99
3 4 99
4 5 99
*/
弱弱不会当前弧,求助!!
by Gao_yc @ 2022-05-28 22:35:09
答案没开long long啊。
by YBaggio @ 2022-05-31 21:19:00
没开longlong见祖宗