UVa 12093 Protecting Zonk

题目

◇题目传送门◆（由于UVa较慢，这里提供一份vjudge的链接）
◇题目传送门（vjudge）◆

题目大意

有$N$个节点构成一个树形结构的图。现有两种机器A，B。A的花费为$C_1$，B的花费为$C_2$。若在某个节点上放一个A机器，则与该节点相连的边被覆盖；若在某节点上放一个B机器，则与该节点相连的边及其相邻节点相连的边会被覆盖。求将所有边覆盖的最小花费。

思路

这是一棵无根树，显然我们要人为的给它一个根。所以我们以1为它的根。

于是这道题变成了很明显的树形DP。但是状态非常复杂。。。

定义状态：

1. $f[u][0]$：$u$不安装任何机器，且保证其与儿子相连得到边全部被儿子覆盖的最小花费；
2. $f[u][1]$：在$u$安装一台A机器的最小花费；
3. $f[u][2]$：在$u$安装一台B机器的最小花费；
4. $f[u][3]$：$u$及$u$的儿子都不安装任何机器，$u$与其儿子的边全部被$u$的父亲覆盖；

注意：在$u$的儿子节点处安装一个B机器等同于在$u$安装一个A机器

我们逐个来分析状态：

对于$f[u][0]$，此时，$u$的儿子需要安装A机器或者B机器，则此状态转移到$\min(f[v][1],f[v][2])$（$v$是$u$的一个儿子）；

对于$f[u][1]$，此时，$v$有三种选择：不安装、安装A机器、安装B机器，则此状态转移到$\min(f[v][0],f[v][1],f[v][2])$；

注意此时我们仍需要将在$u$安装A机器和在$v$安装B机器的花费作比较！

对于$f[u][2]$，此时，$v$有四种选择，则此状态转移到$\min(f[v][0],f[v][1],f[v][2],f[v][3])$；

对于$f[u][3]$，此时，$v$有三种选择：不安装、安装A机器、安装B机器，则此状态转移到$\min(f[v][0],f[v][1],f[v][2])$

所以可列出状态转移方程：
$f[u][0]=\sum\min(f[v][1],f[v][2])\\f[u][1]=\sum\min(f[v][0],f[v][1],f[v][2])+\min(C_1,f[v][2]-\min(f[v][0],f[v][1],f[v][2]))\\f[u][2]=\sum\min(f[v][0],f[v][1],f[v][2],f[v][3])+C_2\\f[u][3]=\sum\min(f[v][0],f[v][1],f[v][2])$

其中，$v$是$u$的儿子。

边界条件为：$f[u][0]=f[u][1]=0,f[u][1]=C_1,f[u][2]=C_2$。其中，$u$是叶子节点。

答案即为$\min(f[1][0],f[1][1],f[1][2])$

正解代码

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;const int Maxn=10000;
const int INF=0x7f7f7f7f;struct Edge {int to;Edge *nxt;
}e[Maxn*2+5];
Edge *ecnt,*G[Maxn+5];
void AddEdge(int u,int v) {Edge *p=++ecnt;p->to=v;p->nxt=G[u],G[u]=p;
}
int N,C1,C2;
int f[Maxn+5][4];void DFS(int u,int fa) {f[u][0]=f[u][1]=f[u][3]=0;f[u][2]=C2;int t=INF;for(Edge *p=G[u];p!=NULL;p=p->nxt) {int v=p->to;if(v==fa)continue;DFS(v,u);f[u][0]+=min(f[v][1],f[v][2]);int tmp=min(f[v][0],min(f[v][1],f[v][2]));f[u][1]+=tmp;f[u][2]+=min(tmp,f[v][3]);f[u][3]+=tmp;t=min(t,f[v][2]-tmp);}f[u][1]+=min(C1,t);
}int main() {#ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifwhile(scanf("%d %d %d",&N,&C1,&C2)!=EOF&&N) {memset(f,0,sizeof f);memset(G,0,sizeof G);ecnt=&e[0];for(int i=1;i<N;i++) {int u,v;scanf("%d %d",&u,&v);AddEdge(u,v);AddEdge(v,u);}DFS(1,-1);printf("%d\n",min(min(f[1][0],f[1][1]),f[1][2]));}return 0;
}