hdu 6214 : Smallest Minimum Cut 【网络流】

题目链接

ISAP写法

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

namespace FastIO

{

    const static int MX=1e6;

    bool IOerror=;

    char nc()

    {

        static char buf[MX],*p1=buf+MX,*pend=buf+MX;

        if(p1==pend)

        {

            p1=buf;

            pend=buf+fread(buf,,MX,stdin);

            if(pend==p1)

            {

                IOerror=;

                return -;

            }

        }

        return *p1++;

    }

    inline bool blank(char ch)

    {

        return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';

    }

    inline int read(int& x)

    {

        char ch;

        while(blank(ch=nc()));

        if(IOerror) return ;

        for(x=ch-''; (ch=nc())>=''&&ch<=''; x=x*+ch-''); //printf("%d===\n",x);

        return ;

    }

    inline int read(LL& x)

    {

        char ch;

        while(blank(ch=nc()));

        if(IOerror) return ;

        for(x=ch-''; (ch=nc())>=''&&ch<=''; x=x*+ch-''); //printf("%d===\n",x);

        return ;

    }

}

using namespace FastIO;

const int MAXN=,MAXM=,MO=;

const int INF = 0x3f3f3f3f;

struct Edge

{

    int to,next,cap,flow;

    Edge() {}

    Edge(int _to,int _next,int _cap,int _flow)

    {

        to=_to,next=_next,cap=_cap,flow=_flow;

    }

} edge[MAXM]; //注意是MAXM

int tol;

int head[MAXN];

int gap[MAXN],d[MAXN],pre[MAXN],cur[MAXN];

void init()

{

    tol = ;

    memset(head,-,sizeof(head));

}

void addedge(int u,int v,int w)

{

    edge[tol]=Edge(v,head[u],w,);

    head[u]=tol++;

    edge[tol]=Edge(u,head[v],,);

    head[v]=tol++;

}

int isap(int start,int end,int N)

{

    memset(gap,,sizeof(gap));

    memset(d,,sizeof(d));

    memcpy(cur,head,sizeof(head));

    int u = start;

    pre[u] = -;

    gap[] = N;

    int ans = ;

    while(d[start] < N)

    {

        if(u == end)

        {

            int Min = INF;

            for(int i = pre[u]; i != -; i = pre[edge[i^].to])

                if(Min > edge[i].cap - edge[i].flow)

                    Min = edge[i].cap - edge[i].flow;

            for(int i = pre[u]; i != -; i = pre[edge[i^].to])

            {

                edge[i].flow += Min;

                edge[i^].flow -= Min;

            }

            u = start;

            ans += Min;

            continue;

        }

        bool flag = false;

        int v;

        for(int i = cur[u]; i != -; i = edge[i].next)

        {

            v = edge[i].to;

            if(edge[i].cap - edge[i].flow && d[v]+ == d[u])

            {

                flag = true;

                cur[u] = pre[v] = i;

                break;

            }

        }

        if(flag)

        {

            u = v;

            continue;

        }

        int Min = N;

        for(int i = head[u]; i != -; i = edge[i].next)

            if(edge[i].cap - edge[i].flow && d[edge[i].to] < Min)

            {

                Min = d[edge[i].to];

                cur[u] = i;

            }

        gap[d[u]]--;

        if(!gap[d[u]])return ans;

        d[u] = Min+;

        gap[d[u]]++;

        if(u != start) u = edge[pre[u]^].to;

    }

    return ans;

}

int main()

{

    int T;

    read(T);

    while (T--)

    {

        int n,m,s,t;

        read(n),read(m);

        read(s),read(t);

        init();

        for(int i=; i<=m; i++)

        {

            int x,y,z;

            read(x),read(y),read(z);

            addedge(x,y,z*MO+);

        }

        int ans=isap(s,t,n);

        printf("%d\n",ans%MO);

    }

}

Dinic写法

#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

#define LC(x) (x<<1)

#define RC(x) ((x<<1)+1)

#define MID(x,y) ((x+y)>>1)

#define CLR(arr,val) memset(arr,val,sizeof(arr))

#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);

typedef pair<int,int> pii;

//typedef long long LL;

namespace FastIO

{

    const static int MX=1e6;

    bool IOerror=;

    char nc()

    {

        static char buf[MX],*p1=buf+MX,*pend=buf+MX;

        if(p1==pend)

        {

            p1=buf;

            pend=buf+fread(buf,,MX,stdin);

            if(pend==p1)

            {

                IOerror=;

                return -;

            }

        }

        return *p1++;

    }

    inline bool blank(char ch)

    {

        return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';

    }

    inline int read(int& x)

    {

        char ch;

        while(blank(ch=nc()));

        if(IOerror) return ;

        for(x=ch-''; (ch=nc())>=''&&ch<=''; x=x*+ch-''); //printf("%d===\n",x);

        return ;

    }

}

using namespace FastIO;

const int N=;

const int M=;

struct edge

{

    int to,nxt;

    int cap;

    edge() {}

    edge(int _to,int _nxt,int _cap): to(_to),nxt(_nxt),cap(_cap) {}

};

edge E[M << ];

int head[N],tot,d[N];

void init()

{

    CLR(head,-);

    tot=;

}

inline void add(int s,int t,int cap)

{

    E[tot]=edge(t,head[s],cap);

    head[s]=tot++;

    E[tot]=edge(s,head[t],);

    head[t]=tot++;

}

int bfs(int s,int t)

{

    CLR(d,-);

    d[s]=;

    queue<int>Q;

    Q.push(s);

    while(!Q.empty())

    {

        int u=Q.front();

        Q.pop();

        for(int i=head[u]; ~i; i=E[i].nxt)

        {

            int v=E[i].to;

            if(d[v]==- && E[i].cap > )

            {

                d[v]=d[u] + ;

                if(v==t)    return ;

                Q.push(v);

            }

        }

    }

    return ~d[t];

}

int dfs(int s,int t,int f)

{

    if(s==t || !f)

        return f;

    int ret=;

    for(int i=head[s]; ~i; i=E[i].nxt)

    {

        int v=E[i].to;

        if(d[v]==d[s] +  && E[i].cap > )

        {

            int df=dfs(v,t,min(f,E[i].cap));

            if(df>)

            {

                E[i].cap -=df;

                E[i ^ ].cap +=df;

                ret +=df;

                f -=df;

                if(!f)    break;

            }

        }

    }

    if(!ret) d[s]=-;

    return ret;

}

int dinic(int s,int t)

{

    int ret=;

    while (bfs(s,t))

        ret+=dfs(s,t,0x3f3f3f3f);

    return ret;

}

int main()

{

    int T;read(T);

    while(T--)

    {

        init();

        int n,m,s,t;

        read(n),read(m);

        read(s),read(t);

        while(m--)

        {

            int u,v,c;

            read(u),read(v),read(c);

            add(u,v,c*+);

        }

        printf("%d\n",dinic(s,t)%);

    }

}

=========================================================================================

9.22更新

根据刘汝佳的板子，自己改编一下后如下（希望以后可以一直用

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

namespace FastIO

{

    const static int MX=1e6;

    bool IOerror=;

    char nc()

    {

        static char buf[MX],*p1=buf+MX,*pend=buf+MX;

        if(p1==pend)

        {

            p1=buf;

            pend=buf+fread(buf,,MX,stdin);

            if(pend==p1)

            {

                IOerror=;

                return -;

            }

        }

        return *p1++;

    }

    inline bool blank(char ch)

    {

        return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';

    }

    inline int read(int& x)

    {

        char ch;

        while(blank(ch=nc()));

        if(IOerror) return ;

        for(x=ch-''; (ch=nc())>=''&&ch<=''; x=x*+ch-''); //printf("%d===\n",x);

        return ;

    }

}

using namespace FastIO;

const int N=;

const int M=;

const int INF=0x3f3f3f3f;

struct Edge

{

    int to,next;

    int flow,cap;    //根据情况设定变量类型

    Edge(){}

    Edge(int _to,int _next,int _cap,int _flow)

    {

        to=_to,next=_next,cap=_cap,flow=_flow;

    }

};

Edge edge[M<<];

int head[N],tot;

int cur[N];

int d[N];

void init()

{

    memset(head,-,sizeof(head));

    tot=;

}

inline void addedge(int u,int v,int cap)

{

    edge[tot]=Edge(v,head[u],cap,);

    head[u]=tot++;

    edge[tot]=Edge(u,head[v],,);

    head[v]=tot++;

}

int bfs(int s,int t)

{

    memset(d,-,sizeof(d));

    queue<int> Q;

    Q.push(s),d[s]=;

    while(!Q.empty())

    {

        int u=Q.front();Q.pop();

        for(int i=head[u];~i;i=edge[i].next)

        {

            int v=edge[i].to;

            if(d[v]==-&&edge[i].cap>edge[i].flow)

            {

                d[v]=d[u]+;

                if(v==t) return ;

                Q.push(v);

            }

        }

    }

    return ~d[t];

}

int dfs(int s,int t,int a)

{

    if(s==t||a==) return a;

    int flow=,df;

//    for(int& i=cur[s];~i;i=edge[i].next)

    for(int i=head[s];~i;i=edge[i].next)

    {

        int v=edge[i].to;

//        if(d[v]==d[s]+1 &&

//            (df=dfs(v,t,min(a,edge[i].cap-edge[i].flow))>0))    //这种写法 hdu6214 TLE

        if(d[v]==d[s]+&&edge[i].cap>edge[i].flow

            &&(df=dfs(v,t,min(a,edge[i].cap-edge[i].flow)))>)

        {

            edge[i].flow+=df;

            edge[i^].flow-=df;

            flow+=df;

            a-=df;

            if(a==) break;

        }

    }

    if(flow==) d[s]=-;

    return flow;

}

int dinic(int s,int t)

{

    int ret=;

    while(bfs(s,t))

    {

//        memcpy(cur,head,sizeof(cur));

        ret+=dfs(s,t,INF);

    }

    return ret;

}

int main()

{

    int T;read(T);

    while(T--)

    {

        init();

        int n,m,s,t;

        read(n),read(m);

        read(s),read(t);

        while(m--)

        {

            int u,v,c;

            read(u),read(v),read(c);

            addedge(u,v,c*+);

        }

        printf("%d\n",dinic(s,t)%);

    }

}