- 传统题 1000ms 512MiB
-
说明
太平王世子事件后,陆小凤成了皇上特聘的御前一品侍卫。 皇宫以午门为起点,直到后宫嫔妃们的寝宫,呈一棵树的形状,某些宫殿间可以互相望见。大内保卫森严,三步一岗,五步一哨,每个宫殿都要有人全天候看守,在不同的宫殿安排看守所需的费用不同。 可是陆小凤手上的经费不足,无论如何也没法在每个宫殿都安置留守侍卫。 帮助陆小凤布置侍卫,在看守全部宫殿的前提下,使得花费的经费最少。
输入格式
输入中数据描述一棵树,描述如下: 第一行 n,表示树中结点的数目。 第二行至第 n+1 行,每行描述每个宫殿结点信息,依次为:该宫殿结点标号 i(0<i≤n),在该宫殿安置侍卫所需的经费 k,该边的儿子数 m,接下来 m个数,分别是这个节点的 m个儿子的标号
,
,⋯,
。
对于一个 n 个结点的树,结点标号在 1到 n 之间,且标号不重复。
输出格式
输出最少的经费
样例
输入数据 1
6 1 30 3 2 3 4 2 16 2 5 6 3 5 0 4 4 0 5 11 0 6 5 0
输出数据 1
25
提示
数据范围:对于 100%的数据,0<n≤1500。 -
#include<bits/stdc++.h> using namespace std; int f[10005][3],v[10005],wc[10005],n,k,l; int in[10005],head[10005],to[10005],ne[10005],tot; void add(int u, int v) { ++tot; to[tot]=v; ne[tot]=head[u]; head[u]=tot; } void dfs(int u,int fa) { int d=0x3f3f3f3f; for(int i=head[u];i;i=ne[i]) { int v=to[i]; if(v==fa) continue; dfs(v,u); f[u][0]+=min(f[v][2],f[v][1]); f[u][1]+=min(f[v][2],f[v][1]); d=min(d,f[v][2]-min(f[v][2],f[v][1])); f[u][2]+=min(f[v][2],min(f[v][1],f[v][0])); } f[u][1]+=d; f[u][2]+=wc[u]; } int main(){ scanf("%d",&n); int a,b,c; for(int i=1;i<=n;i++) { cin>>a;cin>>wc[a]>>b; for(int j=1;j<=b;j++) { scanf("%d",&c); add(a,c);in[c]=1; } } int root=1; while(in[root])root++; dfs(root,0); cout<<min(f[root][2],f[root][1]); return 0; }