Saturday, January 26, 2019

[POJ] 1039. Anniversary party

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

  1. #include <iostream>  
  2. #include <vector>  
  3. #include <stdio.h>  
  4.   
  5. using namespace std;  
  6.   
  7. static const int maxn = 6000 + 5;  
  8.   
  9. vector <int> graph[maxn];  
  10. int c[maxn], dp1[maxn], dp2[maxn];  
  11. bool vis[maxn];  
  12.   
  13. inline void dfs(int u, int p)  
  14. {  
  15.     vis[u] = 1;  
  16.     int sum1 = 0, sum2 = 0;  
  17.     for (int v : graph[u])  
  18.     {  
  19.         if (v == p) continue;  
  20.         dfs(v, u);  
  21.         sum1 += dp2[v];  
  22.         sum2 += max(dp1[v], dp2[v]);  
  23.     }  
  24.     dp1[u] = c[u] + sum1;  
  25.     dp2[u] = sum2;  
  26. }  
  27.   
  28. int main()  
  29. {  
  30.     int tnode;  
  31.     scanf("%d", &tnode);  
  32.     for (int i = 1; i <= tnode; i++) scanf("%d", &c[i]);  
  33.     int u, v;  
  34.     while (scanf("%d %d", &u, &v) == 2)  
  35.     {  
  36.         if (u + v == 0) break;  
  37.         graph[u].push_back(v);  
  38.         graph[v].push_back(u);  
  39.     }  
  40.     int ans = 0;  
  41.     for (int i = 1; i <= tnode; i++)  
  42.     {  
  43.         if (!vis[i])  
  44.         {  
  45.             dfs(i, -1);  
  46.             ans += max(dp1[i], dp2[i]);  
  47.         }  
  48.     }  
  49.     printf("%d\n", ans);  
  50. }  

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.