fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define NMAX 50005
  3. using namespace std;
  4. struct node
  5. {
  6.     int u ;
  7.     int v ;
  8.     int price;
  9.     int id;
  10. };
  11.  
  12. int n , m;
  13. long long s;
  14. int DSU[NMAX], sizeDSU[NMAX];
  15. node graph[10*NMAX];
  16. bool check[10*NMAX];
  17. vector<int> location;
  18. long long totalErase=0;
  19.  
  20. int find_root(int  u)
  21. {
  22.     return (DSU[u]==u)?u:DSU[u]=find_root(DSU[u]);
  23. }
  24.  
  25. bool join(int u ,int v)
  26. {
  27.     int root_u = find_root(u);
  28.     int root_v = find_root(v);
  29.  
  30.     if(root_u == root_v)  return false;
  31.  
  32.     if(sizeDSU[root_u] < sizeDSU[root_v])  swap(root_u , root_v);
  33.     DSU[root_v] = root_u;
  34.     sizeDSU[root_u] += sizeDSU[root_v];
  35.     return true;
  36. }
  37.  
  38. void enter()
  39. {
  40.     cin>> n >> m >> s;
  41.     for(int i = 1 ; i <= m ; i++)
  42.     {
  43.         int u , v , c ;
  44.         cin>> u >> v >> c;
  45.         graph[i] = {u , v , c , i};
  46.     }
  47.  
  48.     for(int i = 1 ; i <= n ; i++)
  49.     {
  50.         DSU[i] = i;
  51.         sizeDSU[i]  = 1;
  52.     }
  53.  
  54. }
  55. void process()
  56. {
  57.     sort(graph + 1, graph + m + 1, [](node &a , node &b) {return a.price < b.price; });
  58.  
  59.     for(int i = m ; i >= 1 ; i--)   if( join(graph[i].u , graph[i].v) ) check[i] = true;
  60.  
  61.     for(int i = 1 ; i <= m ; i++)
  62.     {
  63.         if(!check[i] && totalErase + graph[i].price <= s)
  64.         {
  65.             location.push_back(graph[i].id);
  66.             totalErase += graph[i].price;
  67.         }
  68.     }
  69.  
  70.     cout<<location.size()<<'\n';
  71.  
  72.     sort(location.begin() , location.end());
  73.     for(int id : location)  cout<<id<<" ";
  74. }
  75. int main()
  76. {
  77.     ios_base::sync_with_stdio(0);
  78.     cin.tie(nullptr);
  79.     cout.tie(nullptr);
  80.     enter();
  81.     process();
  82.     return 0;
  83. }
  84.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/Q9jVYE
language:
C++14 (gcc 8.3)
created:
84 days 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!