dinic MLE了QAQ

Freddie @ 2019-11-14 08:14:06

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e4 + 50;
const int M = 2e5 + 50;
const int INF = 0x3f3f3f3f;

inline int read(){
    int f=1,s=0;char c;
    for(;c>'9'||c<'0';c=getchar()) if(c=='-') f=-1;
    for(;c<='9'&&c>='0';c=getchar()) s=(s<<3)+(s<<1)+c-'0';
    return f*s;
}

int n,m,s,t;
int head[N],nxt[M],to[M],val[M],cnt=1;
int cur[N],dep[N];

inline void add(int x,int y,int z){
    val[++cnt]=z;
    to[cnt]=y;
    nxt[cnt]=head[x];
    head[x]=cnt;
}

bool bfs(){
    memset(dep,0,sizeof(dep));
    queue<int> q;
    q.push(s);
    dep[s]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        cur[u]=head[u];
        for(int i=head[u];i;i=nxt[i]){
            int v=to[i];
            if(val[i]&&!dep[v]){
                dep[v]=dep[u]+1;
                q.push(v);//cout<<u<<"->"<<v<<endl;
                if(v==t)
                    return 1;
            }
        }
    }
    return 0;
}

int dfs(int u,int flow){
    if(u==t)
        return flow;
    int tmp=0;
    for(int i=cur[u];i;i=nxt[i]){
        cur[u]=i;
        if(!val[i]) continue;
        int v=to[i],f=dfs(v,min(flow,val[i]));
        if(!f||dep[v]!=dep[u]+1) continue;
        tmp+=f;
        val[i]-=f;
        val[i^1]+=f;
        if(flow==tmp)
            break;
    }
    return tmp;
}

int dinic(){
    int maxflow=0;
    while(bfs())
        maxflow+=dfs(s,INF);
    return maxflow;
}

int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    int x,y,z;
    n=read();m=read();s=read();t=read();
    for(int i=1;i<=m;i++){
        x=read();y=read();z=read();
        add(x,y,z);
        add(y,x,0);
    }
    cout<<dinic();
    return 0;
}
/*
4 5 4 3
4 2 30
4 3 20
2 3 20
2 1 30
1 3 40
*/

by Freddie @ 2019-11-14 08:21:23

窝知道了

by Freddie @ 2019-11-14 08:21:36

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e4 + 50;
const int M = 2e5 + 50;
const int INF = 0x3f3f3f3f;

inline int read(){
    int f=1,s=0;char c;
    for(;c>'9'||c<'0';c=getchar()) if(c=='-') f=-1;
    for(;c<='9'&&c>='0';c=getchar()) s=(s<<3)+(s<<1)+c-'0';
    return f*s;
}

int n,m,s,t;
int head[N],nxt[M],to[M],val[M],cnt=1;
int cur[N],dep[N];

inline void add(int x,int y,int z){
    val[++cnt]=z;
    to[cnt]=y;
    nxt[cnt]=head[x];
    head[x]=cnt;
}

bool bfs(){
    memset(dep,0,sizeof(dep));
    queue<int> q;
    q.push(s);
    dep[s]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        cur[u]=head[u];
        for(int i=head[u];i;i=nxt[i]){
            int v=to[i];
            if(val[i]&&!dep[v]){
                dep[v]=dep[u]+1;
                q.push(v);
                if(v==t)
                    return 1;
            }
        }
    }
    return 0;
}

int dfs(int u,int flow){
    if(u==t)
        return flow;
    int tmp=0,v,f;
    for(int i=cur[u];i;i=nxt[i]){
        cur[u]=i;
        if(!val[i]||dep[v=to[i]]!=dep[u]+1) continue;
        if(!(f=dfs(v,min(flow-tmp,val[i])))) continue;
        tmp+=f;
        val[i]-=f;
        val[i^1]+=f;
        if(flow==tmp)
            break;
    }
    return tmp;
}

int dinic(){
    int maxflow=0;
    while(bfs())
        maxflow+=dfs(s,INF);
    return maxflow;
}

int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    int x,y,z;
    n=read();m=read();s=read();t=read();
    for(int i=1;i<=m;i++){
        x=read();y=read();z=read();
        add(x,y,z);
        add(y,x,0);
    }
    cout<<dinic();
    return 0;
}
/*
10 25 3 1
9 3 80
5 10 62
4 2 13
7 2 20
3 10 90
6 10 53
2 3 11
6 3 45
9 5 37
10 9 93
7 8 28
4 5 28
1 2 52
4 5 54
1 2 62
7 4 64
4 3 40
7 3 39
8 2 72
7 5 5
3 6 88
3 2 56
9 2 72
2 1 81
6 7 84
*/

by 辰星凌 @ 2019-11-14 08:29:30

@Freddie %%%网络流巨佬

by Freddie @ 2019-11-14 08:40:37

@辰星凌 您不就是那个落谷日报的吗 orz

我还是看了您的才会了当前弧优化，和多路增广的

虽然变慢了

by saxiy @ 2019-11-14 08:49:46

Orz 然而窝是HLPP党

by Freddie @ 2019-11-14 08:51:51

@saxiy 蛋是，优化它为什么更慢了

by saxiy @ 2019-11-14 09:19:28

@Freddie 可能写丑了qwq 窝HLPP就一个预标号一个gap优化qwq。。不造什么是当前弧优化和多路增广的qwq。。

by Freddie @ 2019-11-14 09:45:17

@saxiy %中和中学的大佬