小胖守皇宫
描述
huyichen世子事件后，xuzhenyi成了皇上特聘的御前一品侍卫。
皇宫以午门为起点，直到后宫嫔妃们的寝宫，呈一棵树的形状；某些宫殿间可以互相望见。大内保卫森严，三步一岗，五步一哨，每个宫殿都要有人全天候看守，在不同的宫殿安排看守所需的费用不同。
可是xuzhenyi手上的经费不足，无论如何也没法在每个宫殿都安置留守侍卫。
帮助xuzhenyi布置侍卫，在看守全部宫殿的前提下，使得花费的经费最少。
格式
输入格式
输入文件中数据表示一棵树，描述如下：
第1行 n，表示树中结点的数目。
第2行至第n+1n+1行，每行描述每个宫殿结点信息，依次为：该宫殿结点标号i（0<i \le n0<i≤n），在该宫殿安置侍卫所需的经费k，该点的儿子数m，接下来m个数，分别是这个节点的m个儿子的标号r_1, r_2, \cdots, r_mr1,r2,⋯,rm。
对于一个n（0 < n \le 15000<n≤1500）个结点的树，结点标号在1到n之间，且标号不重复。保证经费总和不超过2^31-1231−1。
输出格式
输出文件仅包含一个数，为所求的最少的经费。
样例1
样例输入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限制
提示
如图
来源
huyichen
题目链接：
题目大意：
一个树形皇宫，每个结点可以放置看守，看守能够看到相邻的结点，不同结点有不同花费，问将所有点看守住的最小花费。
题目思路：
【树形DP】
F[X][0]表示结点X的父亲放了守卫的最小花费，
F[X][1]表示结点X自身放了守卫的最小花费，
F[X][2]表示结点X和父亲都不放守卫，X的其中一个儿子放了守卫的最小花费。
这样，父亲放了守卫，X可以选择放守卫(F[X][1])，或者可以是 儿子放或不放守卫(F[son][1],F[son][2])
自身放守卫，则儿子都是父亲放了守卫(F[son][0])
其中一个儿子放了守卫，则枚举哪个儿子是最优值。(F[son][1],F[son][0])
这样最终可以推出转移方程。
/******************************************************
Author : Coolxxx
Copyright 2017 by Coolxxx. All rights reserved.
BLOG : http://blog.****.net/u010568270
******************************************************/
#include<bits/stdc++.h>
#pragma comment(linker,"/STACK:1024000000,1024000000")
#define abs(a) ((a)>0?(a):(-(a)))
#define lowbit(a) (a&(-a))
#define sqr(a) ((a)*(a))
#define mem(a,b) memset(a,b,sizeof(a))
#define eps (1e-8)
#define J 10000
#define mod 1000000007
#define MAX 0x7f7f7f7f
#define PI 3.14159265358979323
#define N 1504
using namespace std;
typedef long long LL;
double anss;
LL aans;
int cas,cass;
int n,m,lll,ans;
int f[N][];
bool u[N];
struct xxx
{
int num,c;
int s[N];
}a[N];
void dp(int now)
{
int i,j;
if(u[now])return;
if(!a[now].num)
{
f[now][]=f[now][]=a[now].c;
f[now][]=;
return;
}
for(i=;i<=a[now].num;i++)
dp(a[now].s[i]);
f[now][]=;
for(j=;j<=a[now].num;j++)
{
f[now][]+=min(f[a[now].s[j]][],f[a[now].s[j]][]);
}
f[now][]=MAX;
for(j=;j<=a[now].num;j++)
{
f[now][]=min(f[now][],f[now][]-min(f[a[now].s[j]][],f[a[now].s[j]][])+f[a[now].s[j]][]);
}
f[now][]=a[now].c;
for(j=;j<=a[now].num;j++)
{
f[now][]+=f[a[now].s[j]][];
}
f[now][]=min(f[now][],f[now][]);
}
int main()
{
#ifndef ONLINE_JUDGE
// freopen("1.txt","r",stdin);
// freopen("2.txt","w",stdout);
#endif
int i,j,k;
int x,y,z;
// for(scanf("%d",&cass);cass;cass--)
// for(scanf("%d",&cas),cass=1;cass<=cas;cass++)
// while(~scanf("%s",s))
while(~scanf("%d",&n))
{
//mem(f,0x7f);
for(i=;i<=n;i++)
{
scanf("%d",&x);
scanf("%d%d",&a[x].c,&a[x].num);
for(j=;j<=a[x].num;j++)
{
scanf("%d",&a[x].s[j]);
u[a[x].s[j]]=;
}
}
for(m=;m<=n;m++)if(!u[m])break;
mem(u,);
dp(m);
ans=min(f[m][],f[m][]);
printf("%d\n",ans);
}
return ;
}
/*
//
//
*/