【转】hdu 3947 River Problem 神之网络流

看到AClist里面有dzy就知道是网络流 最后还是没想出来 只好找题解了Orz

基础知识

本题题解 其中那个y[i]前面应该是负号 作者打错了

 判无解的时候是不满流 要用流量判 不要用费用判！！！！

膜拜此题Orz

#include

using namespace std;

const int maxn=2000 + 10, maxm=maxn*maxn*2;

 

const int maxl=999999999;

inline int Min(int a,int b){return a

inline int Max(int a,int b){return a>b?a:b;}

struct st

{

         int y,d;

         int ne;

         int bro;

         int f;

} e[maxm];

int ee;

int st[maxn];

int n,m;

void addedge(int x,int y,int d,int f)

{//给顶点x和y间添加一条费用d,流量f的边

         e[ee].y=y;e[ee].d=d;e[ee].ne=st[x];e[ee].f=f;st[x]=ee++;

         e[ee].y=x;e[ee].d=-1*d;e[ee].ne=st[y];e[ee].f=0;st[y]=ee++;

         e[ee-2].bro=ee-1;e[ee-1].bro=ee-2;

}

int d[maxn],p[maxn];

//spfa所用到起点的最短距离(这里距离相当于cost)和路径记录之前的一个节点

int c[maxn];//spfa所用数组:是否在队列中

int que[maxn],head,tail;//spfa专用队列

int flow=0;

int spfa(int sx,int ex,int n)//求sx到ex的一次费用增广

{//如果没有增广路就返回maxl否则返回费用

         int i,j,k;

         for (i=0;i

         memset(c,0,sizeof(c));//初始化都没进

         d[sx]=0;

         que[head=0]=sx;tail=1;

         c[sx]=1;

         while (head!=tail)//spfa开始

         {

                   k=que[head++];head%=maxn;

                   c[k]=0;

                   for (i=st[k];i!=-1;i=e[i].ne) if (e[i].f)

                            if (d[k]+e[i].d

                            {

                                     d[e[i].y]=d[k]+e[i].d;

                                     p[e[i].y]=i;

                                     if (c[e[i].y]==0)

                                     {

                                               c[e[i].y]=1;

                                               if (e[i].d<0){head=(head-1+maxn)%maxn;que[head]=e[i].y;}

                                               else

                                               {que[tail++]=e[i].y;tail%=maxn;}

                                     }

                            }

         }

         if (d[ex]==maxl) return maxl;//如果无法到达终点返回maxl

         k=maxl;

         for (i=ex;i!=sx;i=e[e[p[i]].bro].y)       k=Min(k,e[p[i]].f);//计算流

         for (i=ex;i!=sx;i=e[e[p[i]].bro].y)//增加反向边

         {

                   e[p[i]].f-=k;

                   e[e[p[i]].bro].f+=k;

         }

         flow+=k;

         return d[ex]*k;//返回费用为流大小*路径长度(cost累加)

}

int w[200],sumw[200];

int fa[200];

int ui[maxn],vi[maxn],li[maxn],ci[maxn];

int toto=0;

void init()

{

         int i,j,k;

         scanf("%d",&n);

 

         for (i=1;i

         {

                   scanf("%d%d",&j,&k);

                   fa[j]=k;

                   scanf("%d",w+j);

         }

 

         memset(st,-1,sizeof(st));

         ee=0;

         toto=0;

         scanf("%d",&m);

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

                   scanf("%d%d%d%d",ui+i,vi+i,li+i,ci+i);

 

 

         for (j=1;j<=m;j++)

                   addedge(ui[j],vi[j],ci[j],li[j]);

         for (i=2;i<=n;i++)

                   addedge(fa[i],i,0,maxl);

 

         memset(sumw,0,sizeof(sumw));

         for (i=2;i<=n;i++)

                   sumw[fa[i]]+=w[i];

         w[1]=0;

         for (i=1;i<=n;i++)

                   if (sumw[i]

                   {

                            addedge(0,i,0,w[i]-sumw[i]);

                            toto+=w[i]-sumw[i];

                   }

                   else

                            if (sumw[i]>w[i])

                                     addedge(i,n+1,0,sumw[i]-w[i]);

}

int main()

{

         int cass,cas=0;

         for (scanf("%d",&cass);cass–;)

         {

                   cas++;

                   init();

                   printf("Case #%d: ",cas);

                   int cost=0;

                   flow=0;

                   while (1)

                   {

                            int k=spfa(0,n+1,n+2);

                            if (k

                                     cost+=k;

                            else

                                     break;

                   }

                   if (flow

                            puts("-1");

                   else

                            printf("%dn",cost);

         }

         return 0;

}