本地与输出一样,交上去73pts

P3376 【模板】网络最大流

shyr @ 2023-01-13 07:41:25

/*Author:luogu uid 357163 shyr*/
#include<bits/stdc++.h>
#define For(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define Rof(i,a,b,c) for(int i=(b);i>=(a);i-=(c))
using namespace std;
typedef long long LL;
typedef double db;
#define int long long 
typedef unsigned long long ULL;
template<typename t> t &read(t &x){
    char c;int f=1;
    while(!isdigit(c=getchar()))f=(c=='-')?-1:1;
    x=c^'0';
    while(isdigit(c=getchar()))x=x*10+(c^'0');
    return x*=f;
}
int n,Nxt[205],m,s,t,u,v,w,cnt=1,nxt[205],dep[205];
LL ans;
struct node{
    int a,b,c,lst;
    void add(int A,int B,int C){
        a=A,b=B,c=C,lst=nxt[a],nxt[a]=cnt;
    }
}g[10001];
bool BFS(){
    memset(dep,0,sizeof(dep));
    dep[s]=1;queue<int>q;q.push(s);
    while(q.size()){
        int x=q.front();q.pop();Nxt[x]=nxt[x];
        for(int i=nxt[x];i;i=g[i].lst){
            int y=g[i].b;
            if(g[i].c&&!dep[y]){
                dep[y]=dep[x]+1;
                q.push(y);
            }
        }
    }
    return dep[t];
}
LL DFS(int x,LL in){
    if(x==t)return in;
    LL out=0;
    for(int i=Nxt[x];i&&in;i=g[i].lst){
        Nxt[x]=i;int y=g[i].b;LL val=g[i].c;
        if(val&&dep[y]==dep[x]+1){
            LL res=DFS(y,min(in,val));
            g[i].c-=res,g[i^1].c+=res;
            in-=res,out+=res;
        }
    }
    if(!out)dep[x]=-1;
    return out;
}
#define LOCAL
signed main(){
    #ifdef LOCAL
        freopen("P3376_8.in","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    read(n),read(m),read(s),read(t);
    For(i,1,m,1){
        read(u),read(v),read(w);
        g[++cnt].add(u,v,w);
        g[++cnt].add(v,u,0);
    }
    while(BFS())ans+=DFS(s,1e18);
    printf("%lld\n",ans);
    return 0;
}

下了数据#8本地跑的答案是 37381805875,和 out 一样。

但是显示 wrong answer On line 1 column 9, read 9, expected 8.

求问。


by shyr @ 2023-01-13 07:43:04

请忽略 #define LOCAL,提交时显然注释了。


by Sunny郭 @ 2023-01-26 11:09:50

g数组开太小了,本地评测机好像不爆


|