16
2019
08

信息学一本通-1579:皇宫看守 树形dp

一棵树有 N 个节点,现在需要将所有节点都看守住,如果我们选择了节点 i,那么节点 i 本身,节点 i 的父亲和儿子都会被看守住,每个节点有一个选择代价,求完成任务所需要的最小的代价。

显然这是一道树形DP。根据每个节点其实有只有三个状态:①被自己看守;②被儿子看守;③被父亲看守。

我们设这三种状态分别为 F1,F2,F3。当然最终作为答案的根节点没有父亲就从 F1,F2 里面选小的。

接下来我们要考虑怎么转移。

首先看 F1,我们规定 F1[ i ] 代表的是 i 节点被自己看守且以 i 为根的子树都已被看守的最小代价,也就是说一定会选择 i 节点自己,答案中必定会加入选择他自己的代价 Wi。因为这个点会被自己看管,所以只要考虑在其儿子的三个状态中选一个最小的,保证这个节点下面的子树都已被看守就行了。

所以 F1[ i ] += min{ F1[ Si ], F2[ Si ], F3[ Si ] } + w[ i ]其中 Si 代表 i 节点的儿子。

接下来看 F2,我们规定 F2[ i ] 代表 i 节点被儿子看守且以 i 为根的子树都已被看守的最小代价,也就是说一定不选 i 节点,但是至少要在 i 节点的儿子中选择一个而且最多也就选一个,因为代价是正数,选一个就能把 i 看住,就不需要选择多余的点在增加代价了。因为 i 节点不能被选,所以只能在其儿子的 F1, F2 状态中选择小的( F3[ Si ] 代表选择 i 节点,所以不能用 F3[ Si ] ),来保证其子树都已被看守。

所以 F2[ i ] += min{ F1[ Si ], F2[ Si ] } + t。

t 代表选择一个儿子的最小代价:t = F1[ Si ] - min{ F1[ Si ], F2[ Si ] },   (这句话不太好理解,把t代入F2[i]里面去理解)

顺便解释一下 t 的转移:我们从 Si 被看管的代价中选一个最小的,如果是 F1,那么说明 Si 已经被选,就不用再加 W[ Si ] 了,如果是 F2, 那么 F1 - F2 = W[ i ]。 


最后看 F3,我们规定 F3[ i ] 代表 i 节点被父亲看守且以 i 为根的子树都已经被看守的最小代价,也就是说一定不选 i 节点和其儿子节点,必须选择他的父亲。因为必须选择父亲,那么 i 一定会被父亲看守,那么我们只要保证其下面的子树都已被看守,就是在儿子的 F1, F2 中选一个小的,因为还是不能选 i,所以其儿子的 F3 状态仍然不用考虑。

所以 F3[ i ] += min{ F1[ Si ], F2[ Si ]}。


#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 20000;
struct Node{
	int to;
	int next;
	int length;
};
Node edge[20000];
int w[20000]={0};
int tot=0,head[20000];
void addedge(int u,int v,int w){
	edge[++tot].to=v;
	edge[tot].length=w;
	edge[tot].next=head[u];
	head[u]=tot;
	return ;
}
int num=0,pos=0;
//int first;
int d[20000]={0};
int ans=0;
int f1[MAX_N], f2[MAX_N], f3[MAX_N];

int visited[20000]={0};

void dfs(int x,int father){
    int p = 0x7fffffff;
	f1[x] = f2[x] = f3[x] = 0;
	//cout<<x<<" ";
	//visited[x]=1;
	
	for(int i=head[x];i!=-1;i=edge[i].next){
		int v=edge[i].to;
		if(v==father) continue;
		//if(!visited[v])
		dfs(v,x);
	    f1[x] += min(f1[v], min(f2[v], f3[v]));
		f2[x] += min(f1[v], f2[v]);
		int t = f1[v] - min(f1[v], f2[v]);
		p = min(p, t);
		f3[x] += min(f1[v], f2[v]); 
	}
	f2[x] += p; f1[x] += w[x];
	return ;
}
int main(){
	memset(head,-1,sizeof(head));
	int n,u,v,num;
	cin>>n;
	for(int i=1;i<=n;i++){
	    cin>>u;
	    cin>>w[u];
	    cin>>num;
	    
	    for(int j=1;j<=num;j++){
	        cin>>v;
	       
	        addedge(u,v,1);
            addedge(v,u,1);
	    }
	}
	

    dfs(1,0);
    
    ans=min(f1[1],f2[1]);
    cout<<ans;
        
	return 0;
}






« 上一篇 下一篇 »

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。