注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Boleyn Su's Blog

 
 
 
 
 

日志

 
 

SGU194[Reactor Cooling]  

2010-07-02 21:57:26|  分类: 信息学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

还是上下界网络流。

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 200

#define MAXM 1000000

 

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

 

int N,M;

int i[MAXM],j[MAXM],lij[MAXM],cij[MAXM];

RTF rtf;

int total;

RTF::edge* f[MAXM];

 

void build_network(RTF* that)

{

     scanf("%d%d",&N,&M);

     that->V=N+2;

     that->s=0;

     that->t=N+1;

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

     {

         scanf("%d%d%d%d",i+k,j+k,lij+k,cij+k);

         that->add_edge(that->s,j[k],lij[k]);

         that->add_edge(i[k],that->t,lij[k]);

         that->add_edge(i[k],j[k],cij[k]-lij[k]);

         f[k]=that->adj[j[k]];

         total+=lij[k];

     }

}

 

int main()

{

    int flow=rtf.relabel_to_front(build_network);

    if (flow!=total) printf("NO\n");

    else

    {

        printf("YES\n");

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

            printf("%d\n",lij[k]+f[k]->c);

    }

    return 0;

}

 

  评论这张
 
阅读(513)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018