WA 10pts求调

P3376 【模板】网络最大流

凌日潮汐 @ 2023-06-10 19:48:15

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

int n,m,s,t,head[201],now[201],dep[201],cnt;
struct edge{
    int v,w,next;
}e[10005];

void add(int u,int v,long long w) {
    e[++cnt]={v,w,head[u]};
    head[u]=cnt;
    e[++cnt]={v,0,head[v]};
    head[v]=cnt;
}

bool bfs(){
    for(int i=1;i<=n;i++)dep[i]=-1;
    queue<int> q;
    q.push(s);
    dep[s]=0;
    now[s]=head[s];
    while(!q.empty()) {
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=e[i].next) {
            int v=e[i].v;
            if(e[i].w>0&&dep[v]==-1) {
                q.push(v);
                now[v]=head[v];
                dep[v]=dep[x]+1;
                if(v==t)return 1;
            }
        }
    }
    return 0;
}

long long dfs(int x,long long sum){
    if(x==t)return sum;
    long long k,res=0;
    for(register int i=now[x];i&&sum;i=e[i].next){
        now[x]=i;
        int v=e[i].v;
        if(e[i].w>0&&(dep[v]==dep[x]+1)) {
            k=dfs(v,min(sum,(long long)(e[i].w)));
            if(k==0)dep[v]=-1;
            e[i].w-=k;
            e[i^1].w+=k;
            res+=k;
            sum-=k;
        }
    }
    return res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> s >> t;
    for(int i=1;i<=m;i++) {
        int u,v,w;
        cin >> u >> v >> w;
        add(u,v,w);
    }
    long long ans=0;
    while(bfs())ans+=dfs(s,1e18);
    cout << ans << endl;
    return 0;
}

最后一个点WA了

评测记录


by 凌日潮汐 @ 2023-06-10 19:53:05

在线等,急


by 阿丑 @ 2023-06-10 20:30:42

cnt 初值应该是奇数;反向边加错了。


by 阿丑 @ 2023-06-10 20:31:28

另外 WA 10pts 一般指的是 WA 了,总共获得了 10 分吧(


by 凌日潮汐 @ 2023-06-10 20:33:19

ThX


by 凌日潮汐 @ 2023-06-10 20:34:55

@阿丑 问题是,改了之后变成WA 80pts了。

评测只因录


by 阿丑 @ 2023-06-10 21:20:10

@PatrickChen cnt 初值不能是 -1,之前口误了;反向边加错了……


|