STUDENT00 @ 2022-12-14 17:14:41
代码如下:
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=205;
const int INF=1e18;
int n,m,s,t,cur[N],l[N],ans,to[N][N];
vector<pair<int,int> > g[N];
bool bfs(){
memset(l,-1,sizeof(l));
memset(cur,0,sizeof(cur));
l[s]=0;
queue<int> q;
q.push(s);
while(!q.empty()){
int now=q.front();
q.pop();
for(int i=0;i<g[now].size();i++){
int t=g[now][i].first,s=g[now][i].second;
if(l[t]==-1&&s){
l[t]=l[now]+1;
q.push(t);
}
}
}
return l[t]!=-1;
}
int dfs(int now,int mins){
if(now==t) return mins;
int sum=mins;
for(int i=cur[now];i<g[now].size()&∑i++){
cur[now]=i;
int t=g[now][i].first,s=g[now][i].second;
if(s&&l[t]==l[now]+1){
int p=dfs(t,min(mins,s));
sum-=p;
g[now][i].second-=p;
g[t][to[t][now]].second+=p;
}
}
return mins-sum;
}
signed main(){
scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
while(m--){
int x,y,z;
scanf("%lld%lld%lld",&x,&y,&z);
to[x][y]=g[x].size();
g[x].push_back(make_pair(y,z));
to[y][x]=g[y].size();
g[y].push_back(make_pair(x,0));
}
while(bfs()) ans+=dfs(s,INF);
printf("%lld",ans);
return 0;
}
by ListenSnow @ 2022-12-14 17:38:12
@YuRuochen dfs 那里
int p=dfs(t,min(mins,s));
改成
int p=dfs(t,min(sum,s));
即可
by STUDENT00 @ 2022-12-14 17:40:08
@ListenSnow 感谢!