River Problem

题意：一个有向树（河流），只有一个汇点1，每条边只有一个出度。有些河道有污染指数xi,必需要治理，有m段路径，可以去覆盖这些，每被覆盖一次，xi降低响应值。

：即给出一些边必需要覆盖的次数，用m段路径去覆盖，每次覆盖有相应费用，求最小费用。

思路：这题被誉为难题，给一个网络流，给出一些边的流量下界，以及给用某些路段流量去流满足要求。这里与正常网络流相悖，是wi>=xi,所以用：

预先加灌法：（预先灌入大流量（相应干道大小灌溉相应流量），要覆盖的减掉，使达不到预期流量，而用添加费用来补充，恰好跑最小费用最大流）

相应河道流量为U-wi（wi为要覆盖次数），再给的路径直接连边。如果没有wi，那么必然最大流为 U*主干道流量。应该有这些污染指数，所以在某些边流量变窄了！，再没有花费路径补充流量的情况下，比如达不到最大流，就无解，这样起到补充作用。

取之官方思路：

这里u取wi最大值略大（50）即可.

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

using namespace std;

const int inf=0x3f3f3f3f;

const int maxv=301,maxe=10001;

int nume=0;int head[maxv];int e[maxe][4];

void inline adde(int i,int j,int c,int w)         //网络流图

{

    e[nume][0]=j;e[nume][1]=head[i];head[i]=nume;

    e[nume][2]=c;e[nume++][3]=w;

    e[nume][0]=i;e[nume][1]=head[j];head[j]=nume;

    e[nume][2]=0;e[nume++][3]=-w;

}

int nume2=0;int head2[maxv];int e2[maxe][4];

void inline adde2(int i,int j,int c,int w)              //原图

{

    e2[nume2][0]=j;e2[nume2][1]=head2[i];head2[i]=nume2;

    e2[nume2][2]=c;e2[nume2++][3]=w;

}

int numfa[maxv];                              //即dp[i]：i的边干道宽度/包含叶子数

int outd[maxv];

int n,m;int ss,tt;

int inq[maxv];int d[maxv]; int pre[maxv];int prv[maxv];

bool spfa(int &sum,int &sumflow)

{

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

    {

        inq[i]=0;

        d[i]=inf;

    }

    queue<int>q;

    q.push(ss);

    inq[ss]=1;

    d[ss]=0;

    while(!q.empty())

    {

        int cur=q.front();

        q.pop();

        inq[cur]=0;

        for(int i=head[cur];i!=-1;i=e[i][1])

        {

            int v=e[i][0];

            if(e[i][2]>0&&d[cur]+e[i][3]<d[v])

            {

                d[v]=d[cur]+e[i][3];

                pre[v]=i;

                prv[v]=cur;

                if(!inq[v])

                {

                    q.push(v);

                    inq[v]=1;

                }

            }

        }

    }

    if(d[tt]==inf)return 0;

    int cur=tt;int minf=inf;

   while(cur!=ss)

    {

        int fe=pre[cur];

        minf=e[fe][2]<minf?e[fe][2]:minf;

        cur=prv[cur];

    }

     cur=tt;

    while(cur!=ss)

    {

        e[pre[cur]][2]-=minf;

        e[pre[cur]^1][2]+=minf;

        cur=prv[cur];

    }

    sum+=d[tt]*minf;

    sumflow+=minf;

    return 1;

}

int sumcost(int &sumflow)

{

    int sum=0;

    while(spfa(sum,sumflow));

    return sum;

}

int dfs_getnumfa(int u)                 // 记录出i所包含的叶子数（源点数）

{

    if(u==0)return 1;

    for(int i=head2[u];i!=-1;i=e2[i][1])

    {

           int v=e2[i][0];

             numfa[u]+=dfs_getnumfa(v);

    }

    return numfa[u];

}

void read_build()

{

       scanf("%d",&n);

       int aa,bb,cc,ww;

        for(int i=0;i<n-1;i++)

        {

            scanf("%d%d%d",&aa,&bb,&cc);

            adde2(bb,aa,0,cc);         //反向建树，原来的是倒的树

            outd[bb]++;

        }

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

        {

            if(outd[i]==0)            //源点

            {

                adde2(i,0,0,0);

            }

        }

        numfa[0]=1;

        dfs_getnumfa(1);

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

      {

          for(int j=head2[i];j!=-1;j=e2[j][1])

          {

              int v=e2[j][0];

              adde(v,i,numfa[v]*50-e2[j][3],0);

          }

      }

      scanf("%d",&m);

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

      {

          scanf("%d%d%d%d",&aa,&bb,&cc,&ww);

          adde(aa,bb,cc,ww);

      }

}

void init()

{

    nume=0;

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

    nume2=0;

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

    memset(numfa,0,sizeof(numfa));

    memset(outd,0,sizeof(outd));

    ss=0;tt=1;

}

int main()

{

    int T;

    scanf("%d",&T);

    for(int ii=1;ii<=T;ii++)

    {

        init();

        read_build();

        int sumflow=0;

        int ans=sumcost(sumflow);

        if(sumflow!=numfa[1]*50)

          printf("Case #%d: -1\n",ii);

        else

          printf("Case #%d: %d\n",ii,ans);

    }

    return 0;

}

巴特西

hdu3947 给一些已知（需费用）路径去覆盖一些边 //预先加灌法费用流

River Problem

最新文章

热门文章