[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

#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);  
}  

[POJ] 2983 Is the Information Reliable?

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 2983 Is the Information Reliable?
Source            : POJ
Category          : Graph Theory
Algorithm         : System of Difference Constraints
Verdict           : Accepted

#include "iostream"  
#include "queue"  
#include "vector"  
  
using namespace std;  
  
#define inf             123456789  
  
static const int maxn = 1000 + 5;  
  
struct info  
{  
      int v, w;  
      info(int v = 0, int w = 0) : v(v), w(w) {}  
};  
  
vector <info> graph[maxn];  
int n, m;  
int dis[maxn], now[maxn], cnt[maxn];  
  
inline void createGraph()  
{  
      for (int i = 1; i <= n; i++)  
      {  
            graph[0].push_back(info(i, 0));  
      }  
}  
  
inline bool spfa(int src = 0)  
{  
      for (int i = 0; i < maxn; i++)  
      {  
            dis[i] = inf;  
            now[i] = 0;  
            cnt[i] = 0;  
      }  
      queue <int> PQ;  
      PQ.push(src);  
      dis[src] = 0;  
      now[src] = 1;  
      cnt[src] = 1;  
      while (!PQ.empty())  
      {  
            int u = PQ.front(); PQ.pop();  
            now[u] = 0;  
            if (cnt[u] > n) return false;  
            int len = (int)graph[u].size();  
            for (int i = 0; i < len; i++)  
            {  
                  int v = graph[u][i].v;  
                  int w = graph[u][i].w;  
                  if (dis[v] > dis[u] + w)  
                  {  
                        dis[v] = dis[u] + w;  
                        cnt[v]++;  
                        if (!now[v]) now[v] = 1, PQ.push(v);  
                  }  
            }  
      }  
      return true;  
}  
  
int main()  
{  
      //freopen("in.txt", "r", stdin);  
  
      ios_base::sync_with_stdio(false);  
      cin.tie(NULL);  
  
      while (cin >> n >> m)  
      {  
            char t;  
            int u, v, x;  
            for (int e = 1; e <= m; e++)  
            {  
                  cin >> t >> u >> v;  
                  if (t == 'P')  
                  {  
                        cin >> x;  
                        graph[v].push_back(info(u, -x));  
                        graph[u].push_back(info(v, x));  
                  }  
                  else  
                  {  
                        graph[v].push_back(info(u, -1));  
                  }  
            }  
            createGraph();  
            if (spfa() == false) cout << "Unreliable\n";  
            else cout << "Reliable\n";  
            for (int i = 0; i < maxn; i++) graph[i].clear();  
      }  
}