AcWing 1077. 皇宫看守
太平王世子事件后,陆小凤成了皇上特聘的御前一品侍卫。
皇宫各个宫殿的分布,呈一棵树的形状,宫殿可视为树中结点,两个宫殿之间如果存在道路直接相连,则该道路视为树中的一条边。
已知,在一个宫殿镇守的守卫不仅能够观察到本宫殿的状况,还能观察到与该宫殿直接存在道路相连的其他宫殿的状况。
大内保卫森严,三步一岗,五步一哨,每个宫殿都要有人全天候看守,在不同的宫殿安排看守所需的费用不同。
可是陆小凤手上的经费不足,无论如何也没法在每个宫殿都安置留守侍卫。
帮助陆小凤布置侍卫,在看守全部宫殿的前提下,使得花费的经费最少。
输入格式
输入中数据描述一棵树,描述如下:
第一行 n,表示树中结点的数目。
第二行至第 n+1 行,每行描述每个宫殿结点信息,依次为:该宫殿结点标号 i,在该宫殿安置侍卫所需的经费 k,该结点的子结点数 m,接下来 m 个数,分别是这个结点的 m 个子结点的标号 r1,r2,…,rm。
对于一个 n 个结点的树,结点标号在 1 到 n 之间,且标号不重复。
输出格式
输出一个整数,表示最少的经费。
数据范围
1≤n≤1500
6
1 30 3 2 3 4
2 16 2 5 6
3 5 0
4 4 0
5 11 0
6 5 0
25
#include<bits/stdc++.h>
using namespace std;
const int N = 1510;
int n;
int h[N],e[N],w[N],ne[N],idx;
int f[N][3];
bool st[N];
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u)
{
f[u][2]=w[u];
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
dfs(j);
f[u][0]+=min(f[j][1],f[j][2]);
f[u][2]+=min(min(f[j][0],f[j][1]),f[j][2]);
}
f[u][1]=1e9;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
//除了当前遍历到的子节点 其余节点的(s,1)(s,2)的min
f[u][1]=min(f[u][1],f[j][2]+f[u][0]-min(f[j][1],f[j][2]));
}
}
int main()
{
cin>>n;
memset(h,-1,sizeof h);
for(int i=0;i<n;i++)
{
int id,cost,cnt;
cin>>id>>cost>>cnt;
w[id]=cost;
while(cnt--)
{
int ver;
cin>>ver;
add(id,ver);
st[ver]=true;
}
}
int root=1;
while(st[root]) root++;
dfs(root);
cout<<min(f[root][1],f[root][2])<<endl;
return 0;
}