[UVa] 515 - King

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 515 - King
Source            : UVA Online Judge
Category          : Graph Theory
Algorithm         : System of Difference Constraints
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
#define inf           123456789  
  
static const int maxn = 1000 + 5;  
  
struct node  
{  
       int v, w;  
       node(int v = 0, int w = 0) : v(v), w(w) {}  
};  
  
vector <node> graph[maxn];  
int n, m, k;  
  
set <int> allNode;  
  
int dist[maxn];  
bool now[maxn];  
int occ[maxn];  
  
inline bool spfa(int src, int tnode)  
{  
       for (int i = 0; i < maxn; i++)  
       {  
              dist[i] = inf;  
              now[i] = 0;  
              occ[i] = 0;  
       }  
       queue <int> PQ;  
       PQ.push(src);  
       dist[src] = 0;  
       occ[src] = 1;  
       now[src] = 1;  
       while (!PQ.empty())  
       {  
              int u = PQ.front(); PQ.pop();  
              now[u] = 0;  
              for (node it : graph[u])  
              {  
                     int v = it.v;  
                     int w = it.w;  
                     if (dist[v] > dist[u] + w)  
                     {  
                            occ[v]++;  
                            dist[v] = dist[u] + w;  
                            if (!now[v]) now[v] = 1, PQ.push(v);  
                     }  
                     if (occ[v] > tnode) return false; // found negative cycle  
              }  
       }  
       return true;  
}  
  
inline void addEdge(int u, int v, int w)  
{  
       graph[u].push_back(node(v, w));  
}  
  
int main()  
{  
       //freopen("in.txt", "r", stdin);  
       while (cin >> n)  
       {  
              if (n == 0) break;  
              cin >> m;  
              int si, ni, ki;  
              string oi;  
              for (int i = 1; i <= m; i++)  
              {  
                     cin >> si >> ni >> oi >> ki;  
                     int ain = si + ni;  
                     int ai = si - 1;  
                     allNode.insert(ain+1);  
                     allNode.insert(ai+1);  
                     if (oi == "lt") addEdge(ai+1, ain+1, ki-1);  
                     else addEdge(ain+1, ai+1, -(ki+1));  
              }  
              int src = 0;  
              for (int x : allNode) addEdge(src, x, 0);  
              int tnode = allNode.size() + 1;  
              bool negativeCycle = spfa(0, tnode);  
              if (negativeCycle == false) cout << "successful conspiracy\n";  
              else cout << "lamentable kingdom\n";  
              allNode.clear();  
              for (int i = 0; i < maxn; i++) graph[i].clear();  
       }  
}  

[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();  
      }  
}