蒟蒻Dinic蜜汁RE

P3376 【模板】网络最大流

Guess00 @ 2019-03-23 22:14:25

\color{red}\text{RT}
#pragma G++ optimize(2)
#include <bits/stdc++.h>
#define int long long
#define MAXV 200005
#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 Guess00 @ 2019-03-23 22:17:07

QAQ


by Smile_Cindy @ 2019-03-23 22:31:55

@Guess00

把200000改成1000000


by Guess00 @ 2019-03-23 22:38:39

@Alpha 依旧RE


by Smile_Cindy @ 2019-03-23 23:04:37

@Guess00

关O2


|