【题目描述】
一个重要的基地被分成了 n 个连通的区域 ， 出于某种原因 ， 这个基地以某一个区域为核
心，呈一树形分布。
在每个区域里安排警卫的费用是不同的，而每个区域的警卫都可以望见其相邻的区域 。
如果一个区域有警卫或是被相邻区域的警卫望见 ， 那它就是安全的 ， 你的任务是 ： 在确保所
有的区域安全的状态下，使总费用最小。
【输入格式】
第一行 n ，表示树中结点的数目。
接下来 n 行，每行依次是：区域的编号；在此安排警卫的费用；它的子结点的个数 m ，
然后往后 m 个数，为它的子结点编号。
【输出格式】
一行一个数，为最小费用。
【输入样例】
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 <cstdlib>
#include <fstream>
#include <cstring>
#include <iostream> using namespace std; ifstream fin("security.in");
ofstream fout("security.out"); int cnt_node=;//点的个数
bool fuqin[]={false};//判断是否有父节点 int head[]={},cnt=;
struct liansi{
int to;
int nxt;
};
liansi lian_son[]={};//链式前向星 int paying[]={};//每个警卫处要安排警察的费用
int p_state[][]={}; //状态 void add(int a,int b);//链式前向星
void plan(int size,int state); void add(int a,int b){
lian_son[++cnt].to=b;
lian_son[cnt].nxt=head[a];
head[a]=cnt;
return;
} void plan(int size,int state){
if(head[size]==-){//当前节点为数最底部
p_state[size][state]=;//如果状态为父亲看守 花费为0
if(state==){
p_state[size][]=paying[size]; //状态为自己看守 ,花费为自己安排警卫所付的钱
}
return;
} if(state==){//当前节点自己安排警卫
int sum=;
for(int hao=head[size];hao!=-;hao=lian_son[hao].nxt){
int minn=0x7fffff;
int son=lian_son[hao].to; if(p_state[son][]<)plan(son,);//它的儿子可以让父亲看守
minn=min(minn,p_state[son][]);//打擂 求最小 if(p_state[son][]<)plan(son,); //可以自己看守(为便利子孙)
minn=min(minn,p_state[son][]);//打擂 求最小 if(head[son]!=-){//它的儿子也可以让自己儿子看守 这里是说它的儿子有儿子
if(p_state[son][]<)plan(son,);
minn=min(minn,p_state[son][]); //打擂 求最小
}
sum+=minn;//加上所以儿子所用最小值
}
p_state[size][]=sum+paying[size];//再加上自己的安排警卫的钱,为当前节点安排警卫所花费最小金额
} if(state==){//如果让父亲看守
int sum=;
for(int hao=head[size];hao!=-;hao=lian_son[hao].nxt){
int minn=0x7fffff;
int son=lian_son[hao].to; if(p_state[son][]<)plan(son,);//当前节点的儿子要么自己看守
minn=min(minn,p_state[son][]); if(head[son]!=-){
if(p_state[son][]<)plan(son,);//要么有儿子就让儿子看守
minn=min(minn,p_state[son][]);
}
sum+=minn;
}
p_state[size][]=sum;
} if(state==){//表示当前节点由某一儿子看守
int Min=0x7fffff;
for(int hao=head[size];hao!=-;hao=lian_son[hao].nxt){
int sum=, meijv=lian_son[hao].to; //枚举看守儿子节点 for(int hao2=head[size];hao2!=-;hao2=lian_son[hao2].nxt){
int minn=0x7fffff, son=lian_son[hao2].to; if(son!=meijv){//计算非枚举子节点所要花费最小值 if(p_state[son][]<)plan(son,);
minn=min(minn,p_state[son][]);
if(head[son]!=-){
if(p_state[son][]<)plan(son,);
minn=min(minn,p_state[son][]);
}
sum+=minn;
}
}
if(p_state[meijv][]<)plan(meijv,);//计算枚举看守儿子看守的最小值
Min=min(Min,sum+p_state[meijv][]);
}
p_state[size][]=Min;
} return;
} int main(){
fin>>cnt_node; memset(head,-,sizeof(head)); for(int x=;x<=cnt_node;x++){
int s1ze=,paid=,cnt_son=;
fin>>s1ze>>paid>>cnt_son;//输入编号花费与子节点个数
paying[s1ze]=paid;
for(int y=;y<=cnt_son;y++){
int son=;
fin>>son;
fuqin[son]=true;//表示此编号有父节点
add(s1ze,son); //用链式前向星将父节点与子节点连接起来
}
} int gen=;//根
for(int i=;i<=cnt_node;i++){
if(fuqin[i]==false){//如果一个点没有父节点
gen=i;//那么它就是根
break;
}
} memset(p_state,-,sizeof(p_state));//将所有状态默认为-1 plan(gen,); //表示它自己放警卫 自己看守
plan(gen,);//表示让它儿子放警卫 让儿子看守
int ans=min(p_state[gen][],p_state[gen][]);//比较哪种费用最低
cout<<ans;
fout<<ans;
return ;
} /*
核心思路:
划分阶段:
0.由父亲看守,那么它的儿子要么自己看守,要么让它儿子看守
1.有由自己看守,那么自己的儿子可以不看守,也可以看守便利子孙
2.由某一个儿子看守,其它儿子照样可以选择自己看守,还是由自己的儿子看守
*/