SGU176[Flow construction]

上下界网络流,可以去看看胡伯涛的一篇图论的总结

需要注意的是,数据中有一个点#12,它的最小流是负的(讨论里有一个样例来说明),而题目要求必须大于等于0,所以有点变化。

然后,网络流的实现部分是用的算法导论上讲的Relabel-To-Front实现,我已经把它做成了一个模板。

相比于ISAP,Relabel-To-Front的理论时间复杂度更低,但是ISAP通常很快,甚至有时能和HLPP相媲美,不过我还是选择了Relabel-To-Front。不管怎样,它都比以前学的EK快多了。

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-7-2

DESCRIPTION:

$DESCRIPTION

*/

//Test#1: USACO Training ditch

namespace sj

{

          template<int MAXV,int MAXEDGE>

          class Relabel_To_Front

          {

                public:

                struct rtf_edge{int v,c;rtf_edge* next;rtf_edge* back;};

                struct rtf_list{int u;rtf_list* next;};

                typedef struct rtf_edge* edge_pointer;

                typedef struct rtf_list* list_pointer;

                typedef struct rtf_edge edge;

                typedef struct rtf_list list;

                static edge_pointer adj[MAXV];

                static edge_pointer current[MAXV];

                static int e[MAXV];

                static int h[MAXV];

                static int hn[MAXV*2];

                void add_list(int u,list_pointer& tail)

                {

                     static list pool[MAXV];

                     static list_pointer top=pool;

                     tail->u=u;

                     tail->next=top++;

                     tail=tail->next;

                }

                static int V,E;

                static int s,t;

                void add_edge(int u,int v,int c)

                {

                     static edge pool[MAXEDGE];

                     static edge_pointer top=pool;

                     top->v=v;

                     top->c=c;

                     top->next=adj[u];

                     adj[u]=top++;

                     top->v=u;

                     top->c=0;

                     top->next=adj[v];

                     adj[v]=top++;

                     adj[u]->back=adj[v];

                     adj[v]->back=adj[u];

                }

                #define min(a,b) (a)<(b)?(a):(b)

                #define relabel(_u)\

                {\

                        /*GAP*/\

                        hn[h[(_u)]]–;\

                        if (hn[h[(_u)]]==0&&0<h[(_u)]&&h[(_u)]<V)\

                        {\

                           for (int i=0;i<V;i++)\

                           if (i!=s&&h[(_u)]<h[i]&&h[i]<V+1)\

                           {\

                              hn[h[i]]–;\

                              h[i]=V+1;\

                              hn[h[i]]++;\

                           }\

                        }\

                        \

                        h[(_u)]=V*2-1;\

                        for (edge_pointer i=adj[(_u)];i;i=i->next)\

                            if (i->c&&h[(_u)]>h[i->v]+1)\

                               h[(_u)]=h[i->v]+1;\

                        \

                        /*GAP*/\

                        hn[h[(_u)]]++;\

                }

                #define push(_u,_v)\

                {\

                        int df=min(e[(_u)],(_v)->c);\

                        e[(_u)]-=df;\

                        e[(_v)->v]+=df;\

                        (_v)->c-=df;\

                        (_v)->back->c+=df;\

                }

                #define discharge(_u)\

                {\

                        while (e[(_u)])\

                        {\

                              if (!current[(_u)])\

                              {\

                                 relabel((_u));\

                                 current[(_u)]=adj[(_u)];\

                              }\

                              else if (h[(_u)]==h[current[(_u)]->v]+1\

                                       &&current[(_u)]->c)\

                              {\

                                   push((_u),current[(_u)]);\

                              }\

                              else current[(_u)]=current[(_u)]->next;\

                        }\

                }

                int relabel_to_front(void (*build_network)(Relabel_To_Front*))

                {

                    build_network(this);

                   

                    for (edge_pointer i=adj[s];i;i=i->next)

                    {

                        e[s]-=i->c;

                        e[i->v]+=i->c;

                        i->back->c=i->c;

                        i->c=0;

                    }

                   

                    h[s]=V;

                   

                    /*GAP*/

                    hn[0]=V-1;

                    hn[V]=1;

                   

                    list L;

                    list_pointer head=&L,tail=&L;

                    for (int i=0;i<V;i++)

                        if (i!=s&&i!=t)

                           add_list(i,tail);

                   

                    for (int i=0;i<V;i++) current[i]=adj[i];

                   

                    list_pointer pre=0,u=head;

                    while (u!=tail)

                    {

                          int old_h=h[u->u];

                          discharge(u->u);

                          if (h[u->u]>old_h)

                             if (pre)

                             {

                                pre->next=u->next;

                                u->next=head;

                                head=u;

                             }

                          pre=u;

                          u=u->next;

                    }

                    return e[t];

                }

                #undef min

                #undef relabel

                #undef push

                #undef discharge

          };

          template<int MAXV,int MAXEDGE>

          int Relabel_To_Front<MAXV,MAXEDGE>::V;

          template<int MAXV,int MAXEDGE>

          int Relabel_To_Front<MAXV,MAXEDGE>::E;

          template<int MAXV,int MAXEDGE>

          int Relabel_To_Front<MAXV,MAXEDGE>::s;

          template<int MAXV,int MAXEDGE>

          int Relabel_To_Front<MAXV,MAXEDGE>::t;

          template<int MAXV,int MAXEDGE>

          typename Relabel_To_Front<MAXV,MAXEDGE>::edge_pointer

          Relabel_To_Front<MAXV,MAXEDGE>::adj[MAXV];

          template<int MAXV,int MAXEDGE>

          typename Relabel_To_Front<MAXV,MAXEDGE>::edge_pointer

          Relabel_To_Front<MAXV,MAXEDGE>::current[MAXV];

          template<int MAXV,int MAXEDGE>

          int Relabel_To_Front<MAXV,MAXEDGE>::e[MAXV];

          template<int MAXV,int MAXEDGE>

          int Relabel_To_Front<MAXV,MAXEDGE>::h[MAXV];

          template<int MAXV,int MAXEDGE>

          int Relabel_To_Front<MAXV,MAXEDGE>::hn[MAXV*2];

}

#include <stdio.h>

#include <string.h>

using namespace sj;

 

#define MAXN 100

#define MAXM 10000

 

typedef Relabel_To_Front<MAXN+2,4*(MAXN+2)*(MAXN+2)> RTF;

 

int N,M;

int U[MAXM],V[MAXM],Z[MAXM],C[MAXM];

RTF rtf;

int total;

int first_flow;

RTF::edge* edg1[MAXM];

RTF::edge* edg2[MAXM];

RTF::edge* edg3[MAXM];

RTF::edge* edg4;

 

void build_network(RTF* that)

{

     scanf(“%d%d”,&N,&M);

     that->V=N+2;

     that->s=0;

     that->t=N+1;

     for (int i=0;i<M;i++)

     {

         scanf(“%d%d%d%d”,U+i,V+i,Z+i,C+i);

         if (C[i])

         {

            that->add_edge(that->s,V[i],Z[i]);

            that->add_edge(U[i],that->t,Z[i]);

            total+=Z[i];

            edg1[i]=that->adj[that->s];

            edg2[i]=that->adj[U[i]];

         }

         else

         {

             that->add_edge(U[i],V[i],Z[i]);

             edg3[i]=that->adj[U[i]];

         }

     }

     const int oo=~(1<<31);

     that->add_edge(N,1,oo);

     edg4=that->adj[N];

}

void rebuild_network(RTF* that)

{

     first_flow=edg4->back->c;

     edg4->c=edg4->back->c=0;

     for (int i=0;i<M;i++)

         if (C[i])

         {

            edg1[i]->c=edg1[i]->back->c=0;

            edg2[i]->c=edg2[i]->back->c=0;

         }

     memset(RTF::e,0,sizeof(RTF::e));

     memset(RTF::h,0,sizeof(RTF::h));

     memset(RTF::hn,0,sizeof(RTF::hn));

     that->s=0;

     that->t=1;

     that->V=N+1;

     that->add_edge(that->s,N,first_flow);

}

 

int main()

{

    int flow=rtf.relabel_to_front(build_network);

    if (flow!=total) printf(“Impossible\n”);

    else

    {

        int flow=rtf.relabel_to_front(rebuild_network);

        printf(“%d\n”,first_flow-flow);

        for (int i=0;i<M;i++)

            if (C[i]) printf(“%d%c”,Z[i],i+1==M?’\n’:’ ‘);

            else printf(“%d%c”,edg3[i]->back->c,i+1==M?’\n’:’ ‘);

    }

    return 0;

}

 

留下评论

您的电子邮箱地址不会被公开。 必填项已用 * 标注