【题解】警位安排( 树形 DP)

  1 #include <cstdlib>
  2 #include <fstream>
  3 #include <cstring>
  4 #include <iostream>
  5 
  6 using namespace std;
  7 
  8 ifstream fin("security.in");
  9 ofstream fout("security.out");
 10 
 11 int cnt_node=0;//点的个数 
 12 bool fuqin[730]={false};//判断是否有父节点 
 13 
 14 int head[730]={0},cnt=0;
 15 struct liansi{
 16     int to;
 17     int nxt;
 18 };
 19   liansi lian_son[730]={0};//链式前向星 
 20   
 21 int paying[730]={0};//每个警卫处要安排警察的费用 
 22 int p_state[730][3]={0}; //状态 
 23  
 24 void add(int a,int b);//链式前向星 
 25 void plan(int size,int state);
 26   
 27 void add(int a,int b){
 28      lian_son[++cnt].to=b;
 29      lian_son[cnt].nxt=head[a];
 30      head[a]=cnt;
 31      return;
 32 } 
 33 
 34 
 35 void plan(int size,int state){
 36      if(head[size]==-1){//当前节点为数最底部 
 37          p_state[size][state]=0;//如果状态为父亲看守 花费为0 
 38          if(state==1){
 39             p_state[size][1]=paying[size]; //状态为自己看守 ,花费为自己安排警卫所付的钱 
 40          }
 41          return;
 42      }
 43      
 44     if(state==1){//当前节点自己安排警卫  
 45         int sum=0;    
 46         for(int hao=head[size];hao!=-1;hao=lian_son[hao].nxt){
 47           int minn=0x7fffff;    
 48           int son=lian_son[hao].to;
 49         
 50           if(p_state[son][0]<0)plan(son,0);//它的儿子可以让父亲看守  
 51           minn=min(minn,p_state[son][0]);//打擂 求最小 
 52           
 53           if(p_state[son][1]<0)plan(son,1);    //可以自己看守(为便利子孙) 
 54           minn=min(minn,p_state[son][1]);//打擂 求最小 
 55           
 56           if(head[son]!=-1){//它的儿子也可以让自己儿子看守   这里是说它的儿子有儿子 
 57             if(p_state[son][2]<0)plan(son,2);
 58             minn=min(minn,p_state[son][2]);    //打擂 求最小 
 59           }
 60           sum+=minn;//加上所以儿子所用最小值 
 61         }
 62         p_state[size][1]=sum+paying[size];//再加上自己的安排警卫的钱,为当前节点安排警卫所花费最小金额     
 63     }
 64     
 65     if(state==0){//如果让父亲看守 
 66        int sum=0;
 67         for(int hao=head[size];hao!=-1;hao=lian_son[hao].nxt){
 68           int minn=0x7fffff; 
 69           int son=lian_son[hao].to;       
 70              
 71           if(p_state[son][1]<0)plan(son,1);//当前节点的儿子要么自己看守 
 72           minn=min(minn,p_state[son][1]); 
 73              
 74           if(head[son]!=-1){
 75             if(p_state[son][2]<0)plan(son,2);//要么有儿子就让儿子看守 
 76             minn=min(minn,p_state[son][2]);        
 77           }
 78           sum+=minn;
 79          }    
 80           p_state[size][0]=sum;
 81      }
 82      
 83     if(state==2){//表示当前节点由某一儿子看守 
 84        int Min=0x7fffff;
 85        for(int hao=head[size];hao!=-1;hao=lian_son[hao].nxt){
 86          int sum=0, meijv=lian_son[hao].to;    //枚举看守儿子节点 
 87         
 88             for(int hao2=head[size];hao2!=-1;hao2=lian_son[hao2].nxt){
 89               int minn=0x7fffff, son=lian_son[hao2].to;
 90            
 91            if(son!=meijv){//计算非枚举子节点所要花费最小值 
 92            
 93             if(p_state[son][1]<0)plan(son,1);    
 94             minn=min(minn,p_state[son][1]);
 95             if(head[son]!=-1){
 96             if(p_state[son][2]<0)plan(son,2);
 97             minn=min(minn,p_state[son][2]);    
 98             }
 99             sum+=minn;
100            }                      
101             }
102          if(p_state[meijv][1]<0)plan(meijv,1);//计算枚举看守儿子看守的最小值 
103             Min=min(Min,sum+p_state[meijv][1]);
104        }     
105         p_state[size][2]=Min;    
106     }
107     
108     return;    
109 }
110 
111   
112   
113 int main(){
114      fin>>cnt_node;
115      
116      memset(head,-1,sizeof(head));
117      
118      for(int x=1;x<=cnt_node;x++){
119          int s1ze=0,paid=0,cnt_son=0;
120          fin>>s1ze>>paid>>cnt_son;//输入编号花费与子节点个数 
121          paying[s1ze]=paid;
122          for(int y=1;y<=cnt_son;y++){
123                int son=0;
124             fin>>son;           
125             fuqin[son]=true;//表示此编号有父节点 
126             add(s1ze,son); //用链式前向星将父节点与子节点连接起来 
127        }    
128      }
129     
130      int gen=0;//根 
131      for(int i=1;i<=cnt_node;i++){
132          if(fuqin[i]==false){//如果一个点没有父节点 
133             gen=i;//那么它就是根 
134             break;        
135          }
136     }
137          
138      memset(p_state,-1,sizeof(p_state));//将所有状态默认为-1 
139      
140      plan(gen,1); //表示它自己放警卫 自己看守 
141      plan(gen,2);//表示让它儿子放警卫 让儿子看守 
142      int ans=min(p_state[gen][1],p_state[gen][2]);//比较哪种费用最低 
143      cout<<ans;
144      fout<<ans;
145      return 0;
146 }
147 
148 
149 /*
150 核心思路:
151     划分阶段:
152     0.由父亲看守,那么它的儿子要么自己看守,要么让它儿子看守 
153     1.有由自己看守,那么自己的儿子可以不看守,也可以看守便利子孙 
154     2.由某一个儿子看守,其它儿子照样可以选择自己看守,还是由自己的儿子看守          
155 */