紫书动规例题9-12 UVA

题目链接:

题意:

题解:

d[u]:=让u给上级发信最少需要多少工人。假设u有k个节点，则至少c=(kT-1)/100+1个直接下属发信才行。把所有子节点的d值从小到大排序，取前c个加起来就是当前的答案。

代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define MS(a) memset(a,0,sizeof(a))
 5 #define MP make_pair
 6 #define PB push_back
 7 const int INF = 0x3f3f3f3f;
 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
 9 inline ll read(){
10     ll x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 //////////////////////////////////////////////////////////////////////////
16 const int maxn = 1e5+10;
17 
18 int n,T;
19 vector<int> g[maxn];
20 
21 int dfs(int u){
22     int k = g[u].size();
23     if(k == 0) return 1;
24     vector<int> d;
25     for(int i=0; i<k; i++){
26         d.push_back(dfs(g[u][i]));
27     }
28     sort(d.begin(),d.end());
29     int c = (k*T-1)/100 + 1;
30     int ans = 0;
31     for(int i=0; i<c; i++)
32         ans += d[i];
33     return ans;
34 }
35 
36 int main(){
37     while(scanf("%d%d",&n,&T) && (n+T)){
38         for(int i=0; i<=n; i++) g[i].clear();
39         for(int i=1; i<=n; i++){
40             int u = read();
41             g[u].push_back(i);
42         }
43         cout << dfs(0) << endl;
44     }
45 
46     return 0;
47 }

紫书动规 例题9-12 UVA

题目链接:

题意:

题解:

代码:

紫书动规例题9-12 UVA