Author : Dipu Kumar Mohanto
CSE, Batch - 6
BRUR.
Problem Statement : 1039. Anniversary party
Source : POJ
Category : Graph Theory, Dynamic Programing
Algorithm : DP on Tree
Verdict : Accepted
- #include <iostream>
- #include <vector>
- #include <stdio.h>
-
- using namespace std;
-
- static const int maxn = 6000 + 5;
-
- vector <int> graph[maxn];
- int c[maxn], dp1[maxn], dp2[maxn];
- bool vis[maxn];
-
- inline void dfs(int u, int p)
- {
- vis[u] = 1;
- int sum1 = 0, sum2 = 0;
- for (int v : graph[u])
- {
- if (v == p) continue;
- dfs(v, u);
- sum1 += dp2[v];
- sum2 += max(dp1[v], dp2[v]);
- }
- dp1[u] = c[u] + sum1;
- dp2[u] = sum2;
- }
-
- int main()
- {
- int tnode;
- scanf("%d", &tnode);
- for (int i = 1; i <= tnode; i++) scanf("%d", &c[i]);
- int u, v;
- while (scanf("%d %d", &u, &v) == 2)
- {
- if (u + v == 0) break;
- graph[u].push_back(v);
- graph[v].push_back(u);
- }
- int ans = 0;
- for (int i = 1; i <= tnode; i++)
- {
- if (!vis[i])
- {
- dfs(i, -1);
- ans += max(dp1[i], dp2[i]);
- }
- }
- printf("%d\n", ans);
- }
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.