网络流全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 GK0328 @ 2018-12-01 21:55:35

@enor2017


by enor2017 @ 2018-12-01 21:56:19

@可口可乐头

额……额……额……

谢谢dalao


by enor2017 @ 2018-12-01 21:56:50

好了大家不要再理zz的我了%%%


by enor2017 @ 2018-12-01 21:57:00

太丢人了QwQ


by 紬文德斯 @ 2018-12-01 21:57:02

@enor2017 2333~~ @可口可乐头 的是正解


by GK0328 @ 2018-12-01 21:57:08

@enor2017 我可菜了QAQ


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

希望这个帖子快沉下去……

太丢人了


上一页 |