萌新求助,发现网络流模板T了艹,TLE 90pts

P3376 【模板】网络最大流

Spasmodic @ 2020-08-08 20:55:11

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=205,M=5005,INF=0x3f3f3f3f3f3f3f3f; 
ll n,m,s,t,tot=1,hd[N],d[N],ans;
struct edge{ll t,c,nxt;}es[M<<1];
void add(ll u,ll v,ll c){
    es[++tot]=(edge){v,c,hd[u]};hd[u]=tot;
    es[++tot]=(edge){u,0,hd[v]};hd[v]=tot;
}
bool bfs(){
    memset(d,0,sizeof(d));
    queue<ll>q;
    q.push(s);d[s]=1;
    for(ll x;!q.empty();){
        x=q.front();q.pop();
        for(ll i=hd[x];i;i=es[i].nxt)
            if(es[i].c&&!d[es[i].t]){
                q.push(es[i].t);
                d[es[i].t]=d[x]+1;
                if(es[i].t==t)return 1;
            }
    }
    return 0;
}
ll dinic(ll x,ll flow){
    if(x==t)return flow;
    ll rest=flow,k;
    for(ll i=hd[x];i;i=es[i].nxt)
        if(es[i].c&&d[es[i].t]==d[x]+1){
            k=dinic(es[i].t,min(rest,es[i].c));
            es[i].c-=k,es[i^1].c+=k;
            rest-=k;
        }
    if(flow-rest==0)d[x]=-1;
    return flow-rest;
}
int main(){
    scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
    for(ll i=1,u,v,c;i<=m;i++){
        scanf("%lld%lld%lld",&u,&v,&c);
        add(u,v,c);
    }
    for(ll flow=0;bfs();)while((flow=dinic(s,INF)))ans+=flow;
    printf("%lld",ans);
    return 0;
} 

by Eason_AC @ 2020-08-08 21:22:06

@happydef 好吧确实dinic跑起来比EK快qwq


by xiaoyaowudi @ 2020-08-09 08:05:30

orz网络瘤巨佬


by xiaoyaowudi @ 2020-08-09 08:14:25

专题模拟赛的前一天晚上你还在调模板珂海星


by Real_Create @ 2020-08-10 16:17:35

hpdftxdy!


上一页 |