fork(1) download
copy 
  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
comments (?)
stdin
copy 
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
copy 
Standard output is empty
https://ideone.com/gNvux3
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!