UVA 12093 树形DP

题意

有一个N个节点的无根树，两种装置A和B。在某个节点使用节点A，需要C1花费，可以覆盖其相邻的边。在某个节点使用节点B，需要C2花费，可以覆盖其相邻的边以及相邻点的相邻边。求覆盖所有边的最小花费。

题解

设dp[i][j]为第i个节点，第j种状态时所需要的最小花费。状态分四种情况。节点上无装置，但与节点相邻的所有边均已覆盖。节点上有装置A。节点上有装置B。节点上无装置，且与节点相邻的所有边不一定均已覆盖。其中第四种情况不能是最终状态，仅仅是为转移到第三种状态提供一种选择。

注意事项

注意构建边的时候构建的是无向边，因此边数组大小需要MAXN*2。

代码

#include <iostream> #include<cstdio> #include<cstring> #define MAXN 10010 #define min3(a,b,c) min(a,min(b,c)) #define INF 1e9 using namespace std; int tot,head[MAXN]; int dp[MAXN][4]; int n,c,s; struct Edge{ int to,next; }; Edge e[MAXN*2]; void addEdge(int to,int from){ e[tot]=(Edge){to,head[from]}; head[from]=tot++; } void dfs(int u,int pre){ dp[u][0]=0,dp[u][1]=c,dp[u][2]=s,dp[u][3]=0; int ans=0,mi=INF; for(int i=head[u];i!=-1;i=e[i].next){ int v=e[i].to; if(v==pre) continue; dfs(v,u); dp[u][0]+=min(dp[v][1],dp[v][2]); dp[u][1]+=min3(dp[v][0],dp[v][1],dp[v][2]); dp[u][2]+=min(min3(dp[v][0],dp[v][1],dp[v][2]),dp[v][3]); dp[u][3]+=min3(dp[v][0],dp[v][1],dp[v][2]); int x=min3(dp[v][0],dp[v][1],dp[v][2]); ans+=x; mi=min(mi,dp[v][2]-x); } ans+=mi; dp[u][1]=min(dp[u][1],ans); } int main() { while(scanf("%d%d%d",&n,&c,&s)!=EOF){ if(n+c+s==0) break; tot=0; memset(head,-1,sizeof(head)); for(int i=0;i<n-1;i++){ int a,b; scanf("%d%d",&a,&b); addEdge(a,b); addEdge(b,a); } dfs(1,0); printf("%d\n",min3(dp[1][0],dp[1][1],dp[1][2])); } return 0; }