蒟蒻求助

Pete @ 2020-10-23 14:30:02

#include<bits/stdc++.h>
using namespace std;
const long long MAXN=1e10;
long long n,m,s,t,x,y,z,cnt,ans;
bool book[201];
long long dis[201];
long long first[201],next[10001],to[10001],w[10001],now[10001];
void add(long long x,long long y,long long z){
    cnt++;next[cnt]=first[x];first[x]=cnt;to[cnt]=y;w[cnt]=z;
}
inline int dfs(long long k,long long exp){
    if(k==t) return exp;
    long long out=0;
    long long v;
    for(long long i=now[k];i&&exp;i=next[i]){
        v=to[i];
        now[k]=i;
        if((dis[v]==dis[k]+1)&&w[i]){
            long long ll=dfs(v,min(exp,w[i]));
                w[i]-=ll;
                w[i^1]+=ll;
                exp-=ll;
                out+=ll;    

        }
    }
    return out;
}
inline bool bfs(){
    queue<int> q;
    for(long long i=1;i<=n;i++)
        dis[i]=MAXN;    
    q.push(s);
    dis[s]=0;
    now[s]=first[s];
    while(!q.empty()){
        for(long long i=first[q.front()];i;i=next[i]){
            long long v=to[i];
            if(w[i]&&dis[v]==MAXN){
                dis[v]=dis[q.front()]+1;
                q.push(v);
                now[v]=first[v];
                if(v==t) return 1;
            }
        }
        q.pop();
    }
    return 0;
}
int main(){
    scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
    while(m--){
        scanf("%lld%lld%lld",&x,&y,&z);
        add(x,y,z);
        add(y,x,0);
    }
    while(bfs()){
        ans+=dfs(s,MAXN);
    }
    cout<<ans<<endl;
}

by MikeC @ 2020-10-23 14:32:09

支持Pete，支持网络最大流，支持菜鸡，不支持WA，不支持TLE

by zzzsj @ 2020-10-23 14:40:26

支持Pete，支持网络最大流，支持菜鸡，不支持WA，不支持TLE

by JK_LOVER @ 2020-10-23 15:02:26

@Pete 感觉没有太大问题，改了几个地方就过了。

#include<bits/stdc++.h>
using namespace std;
const long long MAXN=1e10;
long long n,m,s,t,x,y,z,cnt = 1,ans;
bool book[2012];
long long dis[2012];
long long first[2021],next[110001],to[101001],w[101001],now[110001];
void add(long long x,long long y,long long z){
    cnt++;next[cnt]=first[x];first[x]=cnt;to[cnt]=y;w[cnt]=z;
}
inline long long dfs(long long k,long long exp){
    if(k == t || exp == 0) return exp;
    long long out=0;// 这里 
    long long v;
    for(long long i=now[k];i;i=next[i]){
        v=to[i];now[k]=i;
        if((dis[v]==dis[k]+1)&&w[i]){
            long long ll=dfs(v,min(exp,w[i]));
                w[i]-=ll;
                w[i^1]+=ll;
                exp-=ll;
                out+=ll;    
                if(exp == 0) break;
        }
    }
    return out;
}
inline bool bfs(){
    queue<int> q;
    for(long long i=1;i<=n;i++)
        dis[i]=MAXN;    
    q.push(s);
    dis[s]=0;
    now[s]=first[s];
    while(!q.empty()){
        for(long long i=first[q.front()];i;i=next[i]){
            long long v=to[i];
            if(w[i]&&dis[v]==MAXN){
                dis[v]=dis[q.front()]+1;
                q.push(v);
                now[v]=first[v];
                if(v==t) return 1;
            }
        }
        q.pop();
    }
    return 0;
}
int main(){
    scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
    while(m--){
        scanf("%lld%lld%lld",&x,&y,&z);
        add(x,y,z);
        add(y,x,0);
    }
    while(bfs()){
//      for(int i = 1;i <= n;i++) now[i] = first[i]; 
        ans+=dfs(s,MAXN);
    }
    cout<<ans<<endl;
}

by JK_LOVER @ 2020-10-23 15:03:40

哦，还是有问题就的 cnt = 1才对，反向边的编号才是对的，好像 dfs 的返回值要设置为 longlong

by Pete @ 2020-10-23 15:06:34

@JK_LOVER 感谢大佬