皇宫看守_今日视点

(资料图片)

题目描述

太平王世子事件后，陆小凤成了皇上特聘的御前一品侍卫。皇宫各个宫殿的分布，呈一棵树的形状，宫殿可视为树中结点，两个宫殿之间如果存在道路直接相连，则该道路视为树中的一条边。已知，在一个宫殿镇守的守卫不仅能够观察到本宫殿的状况，还能观察到与该宫殿直接存在道路相连的其他宫殿的状况。大内保卫森严，三步一岗，五步一哨，每个宫殿都要有人全天候看守，在不同的宫殿安排看守所需的费用不同。可是陆小凤手上的经费不足，无论如何也没法在每个宫殿都安置留守侍卫。帮助陆小凤布置侍卫，在看守全部宫殿的前提下，使得花费的经费最少。

输入格式

输入中数据描述一棵树，描述如下：第一行 n，表示树中结点的数目。第二行至第 n+1 行，每行描述每个宫殿结点信息，依次为：该宫殿结点标号 i，在该宫殿安置侍卫所需的经费 k，该结点的子结点数 m，接下来 m 个数，分别是这个结点的 m 个子结点的标号 r1,r2,…,rm。对于一个 n 个结点的树，结点标号在 1 到 n 之间，且标号不重复。

输出格式

输出一个整数，表示最少的经费。

数据范围

1≤n≤1500

输入样例

61 30 3 2 3 42 16 2 5 63 5 04 4 05 11 06 5 0

输出样例

25

样例解释

在2、3、4结点安排护卫，可以观察到全部宫殿，所需经费最少，为 16 + 5 + 4 = 25。

题目分析代码实现

#include#include#includeusing namespace std;#define int long longconst int N=1505;int h[N],e[2*N],ne[2*N],idx;//dp[i][0]表示结点i由其父节点放置的守卫看守//dp[i][1]表示结点i由其子节点放置的守卫看守 //dp[i][2]表示结点i由该节点放置的守卫看守 int dp[N][3],cost[N],vis[N]; void add(int x,int y){e[idx]=y,ne[idx]=h[x],h[x]=idx++;}void dfs(int u){dp[u][2]=cost[u];int sum=0;for(int i=h[u];~i;i=ne[i]){int j=e[i];dfs(j);//由于dp[u][0]表示结点u由其父节点的守卫看守，所以结点u上不需要放置守卫//所以结点u的子节点一定不能被其父节点u看守，所以不存在dp[j][0]这种状态//所以只取dp[j][1]和dp[j][2]中的最小值即可 dp[u][0]+=min(dp[j][1],dp[j][2]);//由于dp[u][2]表示结点u由其自己的守卫看守，所以结点u上一定放置了守卫//所以结点u的子节点三种状态都存在，所以需要取三种状态的最小值 dp[u][2]+=min(dp[j][0],min(dp[j][1],dp[j][2]));sum+=min(dp[j][1],dp[j][2]);}//dp[u][1]的情况比较复杂，其表示结点u由其子节点放置的守卫看守  //所以结点u上一定没有放置守卫，所以其子节点也只有dp[j][1]和dp[j][2]两种状态//首先计算所有子节点的最小开销和sum//然后逐个遍历判断让哪个子节点作为看守父节点u的结点//求取出该子节点后的开销最小值dp[u][1]=0x3f3f3f3f;for(int i=h[u];~i;i=ne[i]){int j=e[i];dp[u][1]=min(dp[u][1],sum+dp[j][2]-min(dp[j][1],dp[j][2]));}  }signed main(){int n,root=-1;cin>>n;memset(h,-1,sizeof h);for(int i=0;i>x>>c>>k;cost[x]=c;while(k--){cin>>y;add(x,y);vis[y]=1;}}for(int i=1;i<=n;i++)if(!vis[i])root=i;dfs(root);//由于根节点没有父节点，故根节点只有dp[root][1]和dp[root][2]两种状态 //所以求该两种状态的最小值即可 cout<