fork(1) download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef pair<int, int> pii;
  6. typedef vector<int> vi;
  7.  
  8. #define f first
  9. #define s second
  10. #define pb push_back
  11. #define mp make_pair
  12.  
  13. #define FOR(i, a, b) for (int i=a; i<b; i++)
  14. #define F0R(i, a) FOR(i, 0, a)
  15.  
  16. const int MAX = 50005;
  17. const int MOD = 1000000007;
  18.  
  19. vector<pair<pii, int> > g[MAX];
  20. int deg[MAX];
  21. queue<int> q;
  22. vi topo;
  23. int dp[MAX][2];
  24. // int mlp[MAX];
  25. int main() {
  26. int tc = 0;
  27. while (1) {
  28. // memset(mlp, 0, sizeof mlp);
  29. F0R(i, MAX) { g[i].clear(); deg[i] = 0; }
  30. F0R(i, MAX) { F0R(j, 2) { dp[i][j] = 0; } }
  31. topo.clear();
  32.  
  33. tc++;
  34. int n, m;
  35. scanf("%d %d", &n, &m);
  36. if (n+m == 0) { break; }
  37. F0R(i, m) {
  38. int u, v, w; scanf("%d %d %d", &u, &v, &w);
  39. g[u].pb({{v, w}, i+1});
  40. deg[v]++;
  41. }
  42.  
  43. /* topological sort */
  44. FOR(i, 1, n+1) { if (deg[i] == 0) { q.push(i); } }
  45. while (!q.empty()) {
  46. int u = q.front(); q.pop();
  47. topo.pb(u);
  48. for (auto i : g[u]) {
  49. if (--deg[i.f.f] == 0) {
  50. q.push(i.f.f);
  51. }
  52. }
  53. }
  54.  
  55. /* code to find maximum longest path: for debugging */
  56. /*
  57.   vector<pii> ans;
  58.   for (int k=(int)topo.size()-1; ~k; k--) {
  59.   int l = topo[k];
  60.   for (auto i : g[l]) { mlp[l] = max(mlp[l], mlp[i.f.f] + i.f.s); }
  61.   }
  62.   */
  63.  
  64. /* compute the dp[i][0] */
  65. for (int k=(int)topo.size()-2; ~k; k--) {
  66. int i = topo[k];
  67. dp[i][0] = MOD;
  68. vi vals;
  69. for (auto j : g[i]) {
  70. if (dp[j.f.f][0] != MOD) { vals.pb(dp[j.f.f][0]+j.f.s); }
  71. else { vals.clear(); break; }
  72. }
  73. if (!vals.empty()) {
  74. bool ok = true;
  75. for (int j : vals) { if (j != vals[0]) { ok = false; } }
  76. if (ok) { dp[i][0] = vals[0]; }
  77. }
  78. }
  79.  
  80. /* compute the dp[i][1] */
  81. for (int k=(int)topo.size()-2; ~k; k--) {
  82. int i = topo[k];
  83. dp[i][1] = MOD;
  84. vector<pair<pii, int> > vals;
  85. for (auto j : g[i]) {
  86. if (dp[j.f.f][0] != MOD) {
  87. vals.pb({{dp[j.f.f][0]+j.f.s, 0}, j.s});
  88. }
  89. else if (dp[j.f.f][1] != MOD) {
  90. vals.pb({{dp[j.f.f][1] + j.f.s, 1}, j.s});
  91. }
  92. else { vals.clear(); break; }
  93. }
  94. sort(vals.begin(), vals.end());
  95. if (!vals.empty()) {
  96. bool sol = true;
  97. int maxi = vals.back().f.f;
  98. dp[i][1] = maxi;
  99. for (auto j : vals) {
  100. if (j.f.f != maxi) {
  101. if (j.f.s == 1) {
  102. sol = false;
  103. break;
  104. }
  105. ans.pb({j.s, maxi-j.f.f});
  106. }
  107. }
  108. if (!sol) { dp[i][1] = MOD; }
  109. }
  110. }
  111.  
  112. if (dp[topo[0]][1] == MOD) { cout << "Case " << tc << ": No solution" << endl; }
  113. else {
  114. cout << "Case " << tc << ": " << ans.size() << " " << dp[topo[0]][1] << endl;
  115. // for (pii i : ans) { cout << i.f << " " << i.s << endl; }
  116. }
  117. }
  118. }
  119.  
Compilation error #stdin compilation error #stdout 0s 0KB
stdin
Standard input is empty
compilation info
prog.cpp: In function 'int main()':
prog.cpp:105:25: error: 'ans' was not declared in this scope
                         ans.pb({j.s, maxi-j.f.f});
                         ^
prog.cpp:114:46: error: 'ans' was not declared in this scope
             cout << "Case " << tc << ": " << ans.size() << " " << dp[topo[0]][1] << endl;
                                              ^
stdout
Standard output is empty