vovanhoangtuan

1100E - Andrew and Taxi

Nov 25th, 2020
462
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #include <cstdio>
  3.  
  4. using namespace std;
  5.  
  6. int n, m, u, v, c;
  7.  
  8. const int MAX = 100000+10;
  9.  
  10. vector<tuple<int, int, int>> adj;
  11.  
  12. int topo[MAX];
  13.  
  14. bool TopoSort(int cost)
  15. {
  16.     int a[MAX];
  17.     bool visited[MAX];
  18.     vector<int> g[n+1];
  19.  
  20.     bool iFlage = true;
  21.     int dem = 0;
  22.  
  23.     queue<int> temp;
  24.  
  25.     for (int i = 1; i <= n; i++)
  26.     {
  27.         visited[i] = false;
  28.         a[i]= 0;
  29.         topo[i] = 0;
  30.     }
  31.  
  32.     for (int i = 0; i < m; i++)
  33.     {
  34.         int u = get<0>(adj[i]);
  35.         int v = get<1>(adj[i]);
  36.         int w = get<2>(adj[i]);
  37.         if (w > cost)
  38.         {
  39.             g[u].push_back(v);
  40.             a[v]++;
  41.         }
  42.     }
  43.  
  44.     while (iFlage)
  45.     {
  46.         iFlage = false;
  47.         for (int i = 1; i <= n; i++)
  48.         {
  49.             if (visited[i] == false && a[i] == 0)
  50.             {
  51.                 visited[i] = true;
  52.                 temp.push(i);
  53.                 topo[i] = dem++;
  54.             }
  55.         }
  56.         while (!temp.empty())
  57.         {
  58.             int next = temp.front();
  59.             temp.pop();
  60.             for (int i = 0; i < g[next].size(); i++)
  61.             {
  62.                 if (--a[g[next][i]] == 0) iFlage = true;
  63.             }
  64.         }
  65.     }
  66.  
  67.     for (int i = 1; i <= n; i++) if (a[i] > 0) return false;
  68.     return true;
  69.  
  70. }
  71.  
  72. int main()
  73. {
  74.     //freopen("input.txt", "r", stdin);
  75.     int left = 0, right = 0;
  76.  
  77.     cin >> n >> m;
  78.     for (int i = 0; i < m; i++)
  79.     {
  80.         cin >> u >> v >> c;
  81.         adj.push_back(make_tuple(u, v, c));
  82.         right = max(right, c);
  83.     }
  84.  
  85.     while (left <= right)
  86.     {
  87.         int mid = (left + right) / 2;
  88.         bool check = TopoSort(mid);
  89.         if (check) right = mid - 1;
  90.         else left = mid + 1;
  91.     }
  92.  
  93.     TopoSort(left);
  94.  
  95.     int maxCost = 0;
  96.     vector<int> output;
  97.  
  98.     for (int i = 0 ; i < m; i++)
  99.     {
  100.         int u = get<0>(adj[i]);
  101.         int v = get<1>(adj[i]);
  102.         int w = get<2>(adj[i]);
  103.  
  104.         if (w <= left && topo[u] > topo[v])
  105.         {
  106.             maxCost = max(maxCost, w);
  107.             output.push_back(i + 1);
  108.         }
  109.     }
  110.  
  111.     cout << maxCost << " " << output.size() << endl;
  112.     for (auto it:output)
  113.     {
  114.         cout << it << " ";
  115.     }
  116.  
  117.  
  118.     return 0;
  119. }
  120.  
RAW Paste Data