Advertisement
Guest User

Untitled

a guest
Sep 30th, 2014
200
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.32 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2.  
  3. #include <set>
  4. #include <map>
  5. #include <cmath>
  6. #include <time.h>
  7. #include <vector>
  8. #include <string>
  9. #include <cstdio>
  10. #include <cstring>
  11. #include <cassert>
  12. #include <iostream>
  13. #include <algorithm>
  14.  
  15. using namespace std;
  16.  
  17. #define ll long long
  18. #define ld long double
  19.  
  20. const int MAXN = 11000;
  21.  
  22. struct Edge{
  23. int u, v, l;
  24. };
  25.  
  26. int n;
  27. Edge e[MAXN];
  28. vector<int> g[MAXN];
  29.  
  30. int dfs(int u, int par){
  31. int res = 1;
  32. for (int i = 0; i < g[u].size(); i++){
  33. int v = (e[g[u][i]].u == u ? e[g[u][i]].v : e[g[u][i]].u);
  34. if (v != par) res += dfs(v, u);
  35. }
  36. return res;
  37. }
  38.  
  39. int main(){
  40. #ifdef _DEBUG
  41. freopen("input.txt", "r", stdin);
  42. freopen("output.txt", "w", stdout);
  43. #else
  44. freopen("bridges.in", "r", stdin);
  45. freopen("bridges.out", "w", stdout);
  46. #endif
  47. int k, sh, sc;
  48. cin >> n >> k >> sh >> sc;
  49. for (int i = 0; i < n - 1; i++){
  50. cin >> e[i].u >> e[i].v >> e[i].l;
  51. e[i].u--, e[i].v--;
  52. g[e[i].u].push_back(i);
  53. g[e[i].v].push_back(i);
  54. }
  55.  
  56. vector<pair<ll, int> > v;
  57.  
  58. for (int i = 0; i < n - 1; i++){
  59. int inleft = dfs(e[i].u, e[i].v);
  60. v.push_back(make_pair((ll)inleft * (n - inleft) * e[i].l, i));
  61. }
  62.  
  63. sort(v.begin(), v.end());
  64.  
  65. if (sh < sc) reverse(v.begin(), v.end());
  66.  
  67. for (int i = 0; i < k; i++)
  68. cout << v[i].second + 1 << " ";
  69. return 0;
  70. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement