FF全WA求助/kk

P3376 【模板】网络最大流

3a51_ @ 2022-06-02 15:33:24

萌新初学网络流,参考了下题解。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Mod1=998244353;
const int Mod2=1000000007;
const int Inf=1e18;
int gcd(int a,int b){return __gcd(a,b);}
int lcm(int a,int b){return a/gcd(a,b)*b;}
const int N=205;
const int M=10005;
int to[M],nxt[M],val[M],lst[N],cnt,vis[N],n,m,s,t; 
void add(int u,int v,int w){
    to[++cnt]=v;
    val[cnt]=w;
    nxt[cnt]=lst[u];
    lst[u]=cnt;
}
int dfs(int u,int now){
    if(u==t) return now;
    vis[u]=1;
    for(int i=lst[u];i!=0;i=nxt[i]){
        int v=to[i];
        if(vis[v]==1) continue;
        int p=dfs(v,min(now,val[i]));
        if(p>0){
            val[i]-=p;
            val[i+1]+=p;
            return p;
        }
    }
    return 0;
}
void Solve(){
    //coding here...
    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;
    int p=dfs(s,Inf);
    while(p>0){
        memset(vis,0,sizeof(vis));
        ans+=p;
        p=dfs(s,Inf);
    }
    cout<<ans<<endl;
}
signed main(){
    ios::sync_with_stdio(false);
    int _;
    //cin>>_;
    _=1;
    while(_--){
        Solve();
    }
    return 0;
}
//STO 来看我程序的人 Orz

by YamadaRyou @ 2022-06-02 15:37:54

@Tothetime_tolife FF 复杂度不对吧()


by 3a51_ @ 2022-06-02 15:38:59

@cxy2022 但是只会FF


by 3a51_ @ 2022-06-02 15:39:11

不应该AC一部分TLE一部分吗


by YamadaRyou @ 2022-06-02 15:43:52

@Tothetime_tolife 您的inf爆int了。。。


by YamadaRyou @ 2022-06-02 15:44:33

草,define int long long了啊,那我再看看/kk


by 3a51_ @ 2022-06-02 15:44:37

@cxy2022 有宏定义


by rsdbk_husky @ 2022-06-02 15:45:28

@Tothetime_tolife 反向边错了,i 的反向边是 i^1,而且用 ++cnt 的话 cnt 应初始化为奇数。


by 3a51_ @ 2022-06-02 15:45:58

@rsdbk_husky thx


by 3a51_ @ 2022-06-02 15:47:32

还是WA/kk


by 3a51_ @ 2022-06-02 15:49:55

谢谢大家找到问题了忘了回溯


|