EK算法乱入

countryhope_lzc @ 2019-03-24 08:18:43

by 龙之吻—水货 @ 2019-03-24 08:22:54

@countryhope_lzc 为什么非要学EK呢，明明Dinic和EK的难度差不多的喵 QwQ

by Smile_Cindy @ 2019-03-24 08:23:53

Dinic不好么？

#include <bits/stdc++.h>
#define int long long
#define MAXV 1000005
#define inf 2147483647
using std::queue;
using std::vector;
using std::min;
struct edge
{
    int to,cap,rev;
};
vector<edge> G[MAXV];
int i,n,m,s,t,level[MAXV],iter[MAXV];
inline void read(int &x)
{
    short negative=1;
    x=0;
    char c=getchar();
    while(c<'0' || c>'9')
    {
        if(c=='-')
            negative=-1;
        c=getchar();
    }
    while(c>='0' && c<='9')
        x=(x<<3)+(x<<1)+(c^48),c=getchar();
    x*=negative;
}
inline void print(int x)
{
    if (x<0)
        putchar('-'),x=-x;
    if(x>9)
        print(x/10);
    putchar(x%10+'0');
}
inline void add_edge(int from,int to,int cap)
{
    G[from].push_back((edge){to,cap,G[to].size()});
    G[to].push_back((edge){from,0,G[from].size()-1});
}
inline void bfs(int s)
{
    memset(level,-1,sizeof(level));
    queue<int> que;
    level[s]=0;
    que.push(s);
    while(!que.empty())
    {
        int v=que.front();
        que.pop();
        for(int i=0;i<G[v].size();i++)
        {
            edge &e=G[v][i];
            if (e.cap>0 && level[e.to]<0)
                level[e.to]=level[v]+1,que.push(e.to);
        }
    }
}
inline int dfs(int v,int t,int f)
{
    if (v==t)
        return f;
    for (int &i=iter[v];i<G[v].size();i++)
    {
        edge &e=G[v][i];
        if (e.cap>0 && level[v]<level[e.to])
        {
            int d=dfs(e.to,t,min(f,e.cap));
            if (d>0)
            {
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
}
inline int max_flow(int s,int t)
{
    int flow=0,f;
    while (true)
    {
        bfs(s);
        if (level[t]<0)
            return flow;
        memset(iter,0,sizeof(iter));
        while((f=dfs(s,t,inf))>0)
            flow+=f;
    }
}
signed main(void)
{
    read(n),read(m),read(s),read(t);
    for (i=1;i<=m;i++)
    {
        int u,v,w;
        read(u),read(v),read(w);
        add_edge(u,v,w);
    }
    print(max_flow(s,t));
    return 0;
} 

by wjyyy @ 2019-03-24 08:34:36

@countryhope_lzc EK 可过

图应该比较随机

by t162 @ 2019-03-24 08:44:21

HLPP应该可以卡过去

by tgs9311 @ 2019-03-24 08:52:45

肯定能过，也许不用开O2

by countryhope_lzc @ 2019-03-24 09:00:15

@龙之吻—水货 因为刘汝佳上面说最好就是先理解Ek，再把dinic和ISAP当板子用

by countryhope_lzc @ 2019-03-24 09:07:10

Ek已经过了，300ms，比预想中快，可能是随机数据，单纯的模板题，点赞

by countryhope_lzc @ 2019-03-24 09:08:19

@Alpha 现在就去学dinic了