91pts,WA on 10,悬赏关注求调!

P3376 【模板】网络最大流

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()&&sum;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 感谢!


|