[UVa] 11478 - Halum

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

1. #include <bits/stdc++.h>  
2.   
3. using namespace std;  
4.   
5. #define inf                  1e7  
6.   
7. static const int maxn = 1e3 + 5;  
8.   
9. struct edge  
10. {  
11.       int u, v, w;  
12.       edge(int uu = 0, int vv = 0, int ww = 0) : u(uu), v(vv), w(ww) {}  
13. };  
14.   
15. struct node  
16. {  
17.       int v, w;  
18.       node(int vv = 0, int ww = 0) : v(vv), w(ww) {}  
19. };  
20.   
21. vector <edge> edgeList;  
22. vector <node> graph[maxn];  
23. int tnode, tedge;  
24.   
25. int dis[maxn], now[maxn], cnt[maxn];  
26.   
27. bool spfa(int s = 0)  
28. {  
29.       for (int i = 0; i < maxn; i++)  
30.       {  
31.             dis[i] = inf;  
32.             now[i] = 0;  
33.             cnt[i] = 0;  
34.       }  
35.       queue <int> PQ;  
36.       PQ.push(s);  
37.       dis[s] = 0;  
38.       now[s] = 1;  
39.       cnt[s] = 1;  
40.       while (!PQ.empty())  
41.       {  
42.             int u = PQ.front(); PQ.pop();  
43.             now[u] = 0;  
44.             if (cnt[u] > tnode) // negative cycle found  
45.                   return false;  
46.             for (auto &it : graph[u])  
47.             {  
48.                   int v = it.v;  
49.                   int w = it.w;  
50.                   if (dis[v] > dis[u] + w)  
51.                   {  
52.                         dis[v] = dis[u] + w;  
53.                         cnt[v]++;  
54.                         if (!now[v])  
55.                         {  
56.                               now[v] = 1;  
57.                               PQ.push(v);  
58.                         }  
59.                   }  
60.             }  
61.       }  
62.       return true;  
63. }  
64.   
65. bool solve(int m)  
66. {  
67.       for (int i = 0; i < maxn; i++) graph[i].clear();  
68.       for (auto &it : edgeList)  
69.       {  
70.             graph[it.v].push_back(node(it.u, it.w-m));  
71.             graph[0].push_back(node(it.u, 0));  
72.             graph[0].push_back(node(it.v, 0));  
73.       }  
74.       return spfa();  
75. }  
76.   
77. int main()  
78. {  
79.       //freopen("in.txt", "r", stdin);  
80.   
81.       while (scanf("%d %d", &tnode, &tedge) == 2)  
82.       {  
83.             edgeList.clear();  
84.             int maxweight = -inf;  
85.             for (int e = 0; e < tedge; e++)  
86.             {  
87.                   int u, v, w;  
88.                   scanf("%d %d %d", &u, &v, &w);  
89.                   edgeList.push_back(edge(u, v, w));  
90.                   maxweight = max(maxweight, w);  
91.             }  
92.             if (solve(maxweight))  
93.             {  
94.                   printf("Infinite\n");  
95.                   continue;  
96.             }  
97.             int low = 1;  
98.             int high = maxweight;  
99.             int ans = -1;  
100.             while (low <= high)  
101.             {  
102.                   int mid = (low+high)>>1;  
103.                   if (solve(mid)) ans = mid, low = mid+1;  
104.                   else high = mid-1;  
105.             }  
106.             if (ans == -1) printf("No Solution\n");  
107.             else printf("%d\n", ans);  
108.     }  
109. }