BNUOJ 2461 Anniversary party
Party BNUOJ
2023-09-11 14:15:28 时间
Anniversary party
Time Limit: 1000ms
Memory Limit: 65536KB
This problem will be judged on PKU. Original ID: 234264-bit integer IO format: %lld Java class name: Main
There is going to be a party to celebrate the 80-th Anniversary of the Ural State University. The University has a hierarchical structure of employees. It means that the supervisor relation forms a tree rooted at the rector V. E. Tretyakov. In order to make the party funny for every one, the rector does not want both an employee and his or her immediate supervisor to be present. The personnel office has evaluated conviviality of each employee, so everyone has some number (rating) attached to him or her. Your task is to make a list of guests with the maximal possible sum of guests' conviviality ratings.
Input
Employees are numbered from 1 to N. A first line of input contains a number N. 1 <= N <= 6 000. Each of the subsequent N lines contains the conviviality rating of the corresponding employee. Conviviality rating is an integer number in a range from -128 to 127. After that go N – 1 lines that describe a supervisor relation tree. Each line of the tree specification has the form:
L K
It means that the K-th employee is an immediate supervisor of the L-th employee. Input is ended with the line
0 0
L K
It means that the K-th employee is an immediate supervisor of the L-th employee. Input is ended with the line
0 0
Output
Output should contain the maximal sum of guests' ratings.
Sample Input
7 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5 0 0
Sample Output
5
Source
解题:。。。。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib> 10 #include <string> 11 #include <set> 12 #include <stack> 13 #define LL long long 14 #define pii pair<int,int> 15 #define INF 0x3f3f3f3f 16 using namespace std; 17 const int maxn = 6010; 18 int dp[maxn][2],w[maxn],n,in[maxn]; 19 vector<int>g[maxn]; 20 void dfs(int u,int fa){ 21 dp[u][1] = w[u]; 22 for(int i = 0; i < g[u].size(); i++){ 23 if(g[u][i] == fa) continue; 24 dfs(g[u][i],u); 25 dp[u][1] += dp[g[u][i]][0];//u来,g[u][i]不来 26 dp[u][0] += max(dp[g[u][i]][1],dp[g[u][i]][0]); 27 //u不来,g[u][i]来或者不来 28 } 29 } 30 int main() { 31 int i,j,u,v,tmp; 32 while(~scanf("%d",&n)){ 33 for(i = 1; i <= n; i++){ 34 scanf("%d",w+i); 35 g[i].clear(); 36 in[i] = 0; 37 dp[i][0] = dp[i][1] = 0; 38 } 39 for(i = 1; i; i++){ 40 scanf("%d %d",&u,&v); 41 if(u+v == 0) break; 42 g[u].push_back(v); 43 g[v].push_back(u); 44 in[v]++; 45 } 46 for(i = 1; i <= n; i++){ 47 if(!in[i]){dfs(i,-1);break;} 48 } 49 printf("%d\n",max(dp[i][0],dp[i][1])); 50 } 51 return 0; 52 }
相关文章
- E. Third-Party Software - 2 贪心----最小区间覆盖
- hdu 3506 Monkey Party 区间DP+四边形不等式优化
- ZOJ Problem Set - 1730 Crazy Tea Party
- 如何传播一个会议--给Open Party的建议
- ZOJ Problem Set - 1730 Crazy Tea Party
- [ngx-formly] Use 3rd party Form Controls with Angular Formly / Custom type
- [PWA] Cache Third Party Resources from a CDN in a React PWA
- [Angular] Wrap a third party lib into service
- [usaco][舞会灯] party lamps
- [ngx-formly] Use 3rd party Form Controls with Angular Formly / Custom type
- [PWA] Cache Third Party Resources from a CDN in a React PWA
- [Angular] Wrap a third party lib into service
- 使用数据库表查询的方式直接获得CRM服务订单的sold to party信息
- 使用数据库表查询的方式直接获得CRM服务订单的sold to party信息
- 如何获得SAP CRM SalesOrder里involved party的详细信息
- 【Codeforces Round #694 (Div. 2) C】Strange Birthday Party
- 【Henu ACM Round#18 D】Looksery Party
- 【Hello 2018 C】Party Lemonade
- 【习题 8-2 UVA-1610】Party Games
- 【13.91%】【codeforces 593D】Happy Tree Party
- 【BZOJ 1037】[ZJOI2008]生日聚会Party
- 【Uva 1220】Party at Hali-Bula
- Maven自定义上传第三方包到3rd party(第三方无依赖jar和本地扩展类加入maven统一管理)
- HDU 4355 Party All the Time(三分|二分)
- The encryption certificate of the relying party trust identified by thumbprint is not valid
- HDU3062-Party(2-SAT)
- SDUT 2860-生日Party(BFS)
- webrtc报错:Unable to load:src/third_party/usrsctp/BUILD.gn
- 刷题记录:牛客NC25077Bronze Cow Party
- 《论文阅读》DialogXL: All-in-One XLNet for Multi-Party Conversation Emotion Recognition