NOIPer40 @ 2020-10-21 15:05:04

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#define maxn 210
#define maxm 10010
#define ll long long
using namespace std;
ll n,m,s,t,head[maxn],to[maxm],nxt[maxm],cap[maxm],cnt=1,vis[maxn],dep[maxn],ans;
queue<ll> q;
void con(ll u,ll v,ll c){
    to[++cnt]=v;
    cap[cnt]=c;
    nxt[cnt]=head[u];
    head[u]=cnt;
}
void add(ll u,ll v,ll c){
    con(u,v,c);
    con(v,u,0);
}
bool bfs(){
    memset(dep,0,sizeof(dep));
    memset(vis,0,sizeof(vis));
    q.push(s);
    dep[s]=1;
    while(!q.empty()){
        ll f=q.front();
        q.pop();
        for(int i=head[f];i;i=nxt[i]){
            ll ti=to[i];
            if(dep[ti] || !cap[i])
                continue;
            dep[ti]=dep[f]+1;
            q.push(ti);
        }
    }
    return dep[t];
}
ll dfs(ll x,ll flow){
    ll maxf=0,rest=flow;
    vis[x]=1;
    if(x==t){
        ans+=flow;
        return flow;
    }
    for(int i=head[x];i;i=nxt[i]){
        ll ti=to[i],res=0;
        if(!cap[i] || vis[ti])
            continue;
        if(!vis[ti] && cap[i] && dep[ti]==dep[x]+1){
            res=dfs(ti,min(cap[i],rest));
            if(res){
                cap[i]-=res;
                cap[i^1]+=res;
                maxf+=res;
                rest-=res;
            }
        }
    }
    return maxf;
}
int main(){
    scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
    for(int i=1;i<=m;i++){
        ll u,v,c;
        scanf("%lld%lld%lld",&u,&v,&c);
        add(u,v,c);
    }
    while(bfs())
        dfs(s,1e18);
    printf("%lld",ans);
    return 0;
}

by NOIPer40 @ 2020-10-21 15:05:31

tle第8,9点

by MuYC @ 2020-10-21 15:07:07

@NOIPer40 我T了8,10点，第9点300ms 卡过去了....

by NOIPer40 @ 2020-10-21 15:10:48

@Kac_木源崔 az

by MuYC @ 2020-10-21 15:11:30

@NOIPer40 兄弟开个当前弧优化！

by MuYC @ 2020-10-21 15:11:54

@NOIPer40 突然想起自己没加当前弧优化还有DFS剪枝

by NOIPer40 @ 2020-10-21 15:14:26

@Kac_木源崔 我试试看

by JK_LOVER @ 2020-10-21 15:14:55

没有前弧优化还有DFS剪枝，改完大概是这样的。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#define maxn 210
#define maxm 10010
#define ll long long
using namespace std;
ll n,m,s,t,head[maxn],to[maxm],nxt[maxm],cap[maxm],cnt=1,vis[maxn],dep[maxn],ans;
queue<ll> q;
void con(ll u,ll v,ll c){
    to[++cnt]=v;
    cap[cnt]=c;
    nxt[cnt]=head[u];
    head[u]=cnt;
}
void add(ll u,ll v,ll c){
    con(u,v,c);
    con(v,u,0);
}
bool bfs(){
    memset(dep,0,sizeof(dep));
    q.push(s);
    dep[s]=1;
    while(!q.empty()){
        ll f=q.front();
        q.pop();
        for(ll  i=head[f];i;i=nxt[i]){
            ll ti=to[i];
            if(dep[ti] || !cap[i])
                continue;
            dep[ti]=dep[f]+1;
            q.push(ti);
        }
    }
    return dep[t];
}
ll  cur[maxn];
ll dfs(ll x,ll flow){
    ll maxf=0,rest=flow;
    if(x==t || flow == 0){
//        ans+=flow;
        return flow;
    }
    for(ll  i=cur[x];i;i=nxt[i]){
        ll ti=to[i],res=0;
        cur[x] = i;
        if(cap[i] && dep[ti] == dep[x]+1){
            res=dfs(ti,min(cap[i],rest));
            if(res){
                cap[i] -= res;
                cap[i^1] += res;
                maxf += res;
                rest -= res;
                if(rest == 0) break;
            }
        }
    }
    return maxf;
}
int main(){
    scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
    for(int i=1;i<=m;i++){
        ll u,v,c;
        scanf("%lld%lld%lld",&u,&v,&c);
        add(u,v,c);
    }
    ll maxflow = 0;
    while(bfs()) {
        for(int i = 1;i <= n;i++) cur[i] = head[i];
        maxflow += dfs(s,1e18);
    }

    printf("%lld",maxflow);
    return 0;
}

by JK_LOVER @ 2020-10-21 15:16:27

@NOIPer40 开个 cur[] 数组记录当前弧。还有一般有返回值的函数不要这样写。感觉可能有玄学错误。

while(bfs())
        dfs(s,1e18);

by VenusM1nT @ 2020-10-21 15:29:41

您弧优化和判断流空都没加啊……

by NOIPer40 @ 2020-10-21 15:34:17

@JK_LOVER ok a了 谢谢大佬