网络流全T求助QwQ

P3376 【模板】网络最大流

enor2017 @ 2018-12-01 21:45:58

我照着题解看了好几遍了…………

还是没发现哪出问题了,十个点全TLE

求助dalao

#include<cstring>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<iostream>
#include<cctype>
using namespace std;
typedef int ll;
const ll INF=1LL<<30;
const ll MAXN=1e4+50;
const ll EMAXN=1e5+50;
void read(ll &x){
    x=0;char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
}
ll n,m,s,t;
ll head[MAXN],cnt=1;
struct EDGE{
    ll to,next,wei;
}e[EMAXN*2];
ll dep[MAXN];
bool vis[MAXN];
void addedge(ll u,ll v,ll wei){
    e[++cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
    e[cnt].wei=wei;
}
bool bfs(){
    fill(dep,dep+MAXN-1,INF);
    memset(vis,false,sizeof(vis));
    queue<ll> q;
    q.push(s);
    dep[s]=0;
    //vis[s]=true;
    while(!q.empty()){
        ll now=q.front();
        q.pop();
        vis[now]=false;
        for(ll i=head[now];i;i=e[i].next){
            ll v=e[i].to;
            if(dep[v]>dep[now]+1&&e[i].wei){
                dep[v]=dep[now]+1;
                if(!vis[v]){
                    q.push(v);
                    vis[v]=true;
                }
            }
        }
    }
    if(dep[t]!=INF) return true;
    else return false;
}
ll dfs(ll u,ll flow){
    ll thisflow=0;
    if(u==t) return flow;
    for(ll i=head[u];i;i=e[i].next){
        ll v=e[u].to;
        if(e[i].wei&&dep[v]==dep[u]+1){
            if((thisflow=dfs(v,min(flow,e[i].wei)))){
                e[i].wei-=thisflow;
                e[i^1].wei+=thisflow;
                return thisflow;
            }
        }
    }
    return 0;
}
ll maxflow=0;
ll dinic(){
    ll lowflow;
    while(bfs()){
        while(lowflow=dfs(s,INF))maxflow+=lowflow;
    }
    return maxflow;
}
int main(){
    read(n),read(m),read(s),read(t);
    ll x,y,z;
    for(ll i=1;i<=m;++i){
        read(x),read(y),read(z);
        addedge(x,y,z);
        addedge(y,x,0);
    }
    cout<<dinic()<<endl;
    //printf("%lld\n",dinic());
    return 0;
}

by 紬文德斯 @ 2018-12-01 21:50:20

fill是什么鬼= =

要不要我的码风优良常数较小的模板QAQ


by enor2017 @ 2018-12-01 21:51:03

@紬文德斯 我的INF写成这样之后就不能用memset了好慌啊


by 紬文德斯 @ 2018-12-01 21:52:14

@enor2017 哦哦这个意思啊QAQ

你memset 0x3f 或 7f 不就行了嘛QAQ

我帮你再看看


by decoqwq @ 2018-12-01 21:52:33

感觉dfs问题大了吧。。


by enor2017 @ 2018-12-01 21:53:33

@Decoration

蛤?


by GK0328 @ 2018-12-01 21:54:00

@enor2017 SPFA?


by GK0328 @ 2018-12-01 21:54:41

ll v=e[u].to;

@enor2017


by enor2017 @ 2018-12-01 21:54:59

@可口可乐头 额……只是dinic的最大流


by GK0328 @ 2018-12-01 21:55:06

仔细看看这是啥


by GK0328 @ 2018-12-01 21:55:28

你确定不是e[i].to


| 下一页