关于网络最大流

P3376 【模板】网络最大流

Chancylaser @ 2021-07-21 18:04:30

#include<iostream>//网络最大流 
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const long long maxn=5005;
long long n,m;
long long s,t;
long long a,b,c;
struct edge{
    long long e,f;
    long long next;
    long long op;
}ed[maxn<<1];
long long first[maxn];
long long en;
void add(long long s,long long e,long long f){
    en++;
    ed[en].next=first[s];
    first[s]=en;
    ed[en].e=e;
    ed[en].f=f;
    en++;
    ed[en].next=first[e];
    first[e]=en;
    ed[en].e=s;
    ed[en].f=0;
    ed[en].op=en-1;
    ed[en-1].op=en;
    return; 
}
long long depth[100005];
long long dfs(long long now,long long flow){
    if(now==t) return flow;
    long long ans=0;
    for(register int i=first[now];i!=0;i=ed[i].next){
        long long e=ed[i].e, f=ed[i].f , op=ed[i].op;
        if(f!=0&&flow!=0&&depth[e]>depth[now]){
            long long delta=dfs(e,min(f,flow));
            ed[i].f-=delta;
            ed[op].f+=delta;
            flow-=delta;
            ans+=delta;
        }
    }
    return ans;
}
bool bfs(long long s){
    queue<long long> q;
    q.push(s);
    memset(depth,0,sizeof(depth));
    depth[s]=1;
    while(q.size()){
        long long now=q.front();
        q.pop();
        for(register int i=first[now];i!=0;i=ed[i].next){
            long long e=ed[i].e , f=ed[i].f;
            if(depth[e]==0&&f!=0){
                depth[e]=depth[now]+1;
                q.push(e);
            }
        }
    }
    return depth[t]!=0;
}
long long dinic(){
    long long ans=0;
    while(bfs(s))
        ans+=dfs(s,1e12+19);
    return ans;
}
int main(){
    //freopen("qwq.txt","r",stdin);
    cin>>n>>m>>s>>t;
    for(register int i=1;i<=m;i++){
        cin>>a>>b>>c;
        add(a,b,c);
    }
    cout<<dinic();
    return 0;
} 

这是我的代码,有一个点tle了,2天了,还没有调出来,有没有神仙给我看一下呀?


by 幻影星坚强 @ 2021-07-21 18:07:39

要加当前弧优化


by michael_song @ 2021-07-22 08:20:27

@幻影星坚强 我交的时候没优化就过了


by 幻影星坚强 @ 2021-07-22 08:25:28

@michael_song 可是你加了


by michael_song @ 2021-07-22 08:34:16

@幻影星坚强 ? 好吧可能我一开始学的就是要加的 离谱


|