【UVA12093】Protecting Zonk （树形DP）

题意：

　　给定一个有n个节点的无根树，有两种装置A和B，每种都有无限多个。在某个节点X使用A装置需要C1的花费，并且此时与节点X相连的边都被覆盖。在某个节点X使用B装置需要C2的花费，并且此时与节点X相连的边以及与X相连的点相连的边都被覆盖。求覆盖所有边的最小花费。

分析：

　　首先无根树可以先dfs确定根。考虑选择装置A和装置B的影响。

　　装置A只会影响节点u连出去的边。而装置B还会影响u相连的点相连的边，也就是说与节点u距离为2的边也会被影响。

　　也就是说，对于边(u,fa[u])，如果fa[fa[u]]装上装置B,那么这条边就被覆盖。但只有这种情况吗？有一个容易漏的情况就是如果u、v的父亲都是fa[u]，如果在v上装了装置B，那么边(u,fa[u])就被覆盖了。（像我这种想东西不全面的人就容易把这种情况漏掉，导致我后来整个代码重打了一遍~~）

　　而对于装置A，处理过程就相对简单了，下面我只说说我怎么处理装置B的。

　　用了个四维DP，dp[x][a][b][c](a=0~2; b=0~2; c=0~1)表示节点x，选了a装置(0表示不选，1表示装置A，2表示装置B)，fa[x]选了b装置，目前边(u,fa[u])的状态为c。

　　如果c=0，那么u的子节点中一定要有至少一个装上装置B。而对于上述说的装置B的第二种情况，我们也可以用这个一起计算。

　　那么就是两种方案：

　　1、u的子节点中至少有一个装上装置B。

　　2、u的子节点中没有装上装置B的。

　　当符合条件时，取两者的min值即可。

代码如下：

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 #define Maxn 10010

 #define INF 100000010

 int dp[Maxn][][][];

 int first[Maxn],fa[Maxn];

 int n,c1,c2;

 struct node

 {

     int x,y,next;

 }t[*Maxn];int len;

 void ins(int x,int y)

 {

     t[++len].x=x;t[len].y=y;

     t[len].next=first[x];first[x]=len;

 }

 int mymin(int x,int y) {return x<y?x:y;}

 void dfs(int x,int f)

 {

     fa[x]=f;

     for(int i=first[x];i;i=t[i].next) if(t[i].y!=f)

     {

         int y=t[i].y;

         dfs(y,x);

     }

 }

 int ffind(int x,int a,int b,int c)// a->x b->fa c->(x,fa[x])

 {

     if(dp[x][a][b][c]<INF) return dp[x][a][b][c];

     int ans=dp[x][a][b][c];

     int p=(a!=||b==)?:,h=,y,now;

     for(int i=first[x];i;i=t[i].next) if(t[i].y!=fa[x])//sons have at least one B

     {

         y=t[i].y;

         now=mymin(mymin(ffind(y,,a,),ffind(y,,a,)),ffind(y,,a,));

         h+=now;

     }

     for(int i=first[x];i;i=t[i].next) if(t[i].y!=fa[x])

     {

         y=t[i].y;

         now=mymin(mymin(ffind(y,,a,),ffind(y,,a,)),ffind(y,,a,));

         ans=mymin(ans,h-now+ffind(y,,a,));

     }

     if(c!=) //sons have no B

     {

         now=;

         for(int i=first[x];i;i=t[i].next) if(t[i].y!=fa[x])

         {

             y=t[i].y;

             now+=mymin(ffind(y,,a,p),ffind(y,,a,));

         }

         ans=mymin(ans,now);

     }

     if(a==) ans+=c1;

     else if(a==) ans+=c2;

     dp[x][a][b][c]=ans;

     return ans;

 }

 int main()

 {

     while()

     {

         scanf("%d%d%d",&n,&c1,&c2);

         if(n==&&c1==&&c2==) break;

         len=;

         memset(first,,sizeof(first));

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

         {

             int x,y;

             scanf("%d%d",&x,&y);

             ins(x,y);ins(y,x);

         }

         memset(dp,,sizeof(dp));

         dfs(,);

         int ans=INF;

         ans=mymin(ans,ffind(,,,));

         ans=mymin(ans,ffind(,,,));

         ans=mymin(ans,ffind(,,,));

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

     }

     return ;

 }

UVA12093

2016-03-10 17:16:10

巴特西

【UVA12093】Protecting Zonk （树形DP）

最新文章

热门文章