首页 > 代码库 > codevs 1380 没有上司的舞会 - 树形动态规划
codevs 1380 没有上司的舞会 - 树形动态规划
题目描述 Description
Ural大学有N个职员，编号为1~N。他们有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。每个职员有一个快乐指数。现在有个周年庆宴会，要求与会职员的快乐指数最大。但是，没有职员愿和直接上司一起与会。
输入描述 Input Description
第一行一个整数N。(1<=N<=6000)
接下来N行，第i+1行表示i号职员的快乐指数Ri。(-128<=Ri<=127)
接下来N-1行，每行输入一对整数L,K。表示K是L的直接上司。
最后一行输入0,0。
输出描述 Output Description
输出最大的快乐指数。
样例输入 Sample Input
711111111 32 36 47 44 53 50 0
样例输出 Sample Output
5 数据范围及提示 Data Size & Hint
各个测试点1s
按照这个关系建一棵树，然后进行树归，用f[i]表示i职员参加舞会的最大快乐指数之和，g[i]表示i职员不参加舞会的最大快乐指数之和。那么有f[i]为所有i的子节点的g[son[i]]的和，g[i]是i的子节点的g[son[i]]和f[son[i]]最大值的和。
最后的答案在f[1]和g[1]中找最大值。
Code
1 /** 2 * codevs 3 * Problem#1380 4 * Accepted 5 * Time:10ms 6 * Memory:492k 7 */ 8 #include<iostream> 9 #include<sstream> 10 #include<algorithm> 11 #include<cstdio> 12 #include<cstring> 13 #include<cstdlib> 14 #include<cctype> 15 #include<cmath> 16 #include<ctime> 17 #include<map> 18 #include<stack> 19 #include<set> 20 #include<queue> 21 #include<vector> 22 #ifndef WIN32 23 #define AUTO "%lld" 24 #else 25 #define AUTO "%I64d" 26 #endif 27 using namespace std; 28 typedef bool boolean; 29 #define inf 0xfffffff 30 #define smin(a, b) (a) = min((a), (b)) 31 #define smax(a, b) (a) = max((a), (b)) 32 template<typename T> 33 inline boolean readInteger(T& u) { 34 char x; 35 int aFlag = 1; 36 while(!isdigit((x = getchar())) && x != ‘-‘ && x != -1); 37 if(x == -1) { 38 ungetc(x, stdin); 39 return false; 40 } 41 if(x == ‘-‘) { 42 aFlag = -1; 43 x = getchar(); 44 } 45 for(u = x - ‘0‘; isdigit((x = getchar())); u = u * 10 + x - ‘0‘); 46 u *= aFlag; 47 ungetc(x, stdin); 48 return true; 49 } 50 51 typedef class Edge { 52 public: 53 int end; 54 int next; 55 Edge(const int end = 0, const int next = 0):end(end), next(next) { } 56 }Edge; 57 58 typedef class MapManager { 59 public: 60 int ce; 61 int *h; 62 Edge *edge; 63 MapManager():ce(0), h(NULL), edge(NULL) { } 64 MapManager(int points, int edges):ce(0) { 65 h = new int[(const int)(points + 1)]; 66 edge = new Edge[(const int)(edges + 1)]; 67 memset(h, 0, sizeof(int) * (points + 1)); 68 } 69 70 inline void addEdge(int from, int end) { 71 edge[++ce] = Edge(end, h[from]); 72 h[from] = ce; 73 } 74 75 Edge& operator [](int pos) { 76 return edge[pos]; 77 } 78 }MapManager; 79 #define m_begin(g, i) (g).h[(i)] 80 81 int n; 82 int *val; 83 MapManager g; 84 int *f, *g1; 85 int root; 86 87 inline void init() { 88 readInteger(n); 89 val = new int[(const int)(n + 1)]; 90 g = MapManager(n, n); 91 f = new int[(const int)(n + 1)]; 92 g1 = new int[(const int)(n + 1)]; 93 for(int i = 1; i <= n; i++) 94 readInteger(val[i]); 95 int sum = 0; 96 for(int i = 1, a, b; i < n; i++) { 97 readInteger(a); 98 readInteger(b); 99 sum += a;100 g.addEdge(b, a);101 }102 root = n * (n + 1) / 2 - sum;103 }104 105 void treedp(int node, int fa) {106 g1[node] = 0;107 f[node] = val[node];108 for(int i = m_begin(g, node); i != 0; i = g[i].next) {109 int& e = g[i].end;110 if(e == fa) continue;111 treedp(e, node);112 g1[node] += max(g1[e], f[e]);113 f[node] += g1[e];114 }115 }116 117 inline void solve() {118 treedp(root, 0);119 printf("%d", max(g1[root], f[root]));120 }121 122 int main() {123 init();124 solve();125 return 0;126 }
codevs 1380 没有上司的舞会 - 树形动态规划
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。