Advertisement
Guest User

Untitled

a guest
Dec 5th, 2019
116
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.37 KB | None | 0 0
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. int arr[10009][2];
  6. int n;
  7.  
  8. struct edge{
  9. int from,to;
  10. double w;
  11. edge(int from,int to,double w):from(from),to(to),w(w){}
  12.  
  13. bool operator < (const edge &e) const{
  14. return w > e.w;
  15. }
  16. };
  17. vector<edge>adj;
  18. struct UnionFind{
  19. vector<int> parent;
  20. vector<int> rank;
  21. int forests;
  22.  
  23. UnionFind(int n){
  24. parent.resize(n);
  25. rank.resize(n);
  26. forests =n;
  27. for(int i=0 ; i<n ; i++){
  28. parent[i] = i;
  29. rank[i] =1;
  30. }
  31. }
  32. void reset(){
  33. for(int i=0 ; i<n ; i++){
  34. parent[i] = i;
  35. rank[i] =1;
  36. }
  37. forests =n;
  38. }
  39.  
  40. int find_set(int x){
  41. if(x==parent[x])return x;
  42. else parent[x] = find_set(parent[x]);
  43. }
  44.  
  45. void link (int x , int y){
  46. if(rank[x] > rank[y]){
  47. int tmp =x;
  48. x = y;
  49. y = tmp;
  50. }
  51. parent[x] = y;
  52. if(rank[x] == rank[y])rank[y]++;
  53. }
  54. bool union_sets(int x , int y){
  55. x = find_set(x);
  56. y = find_set(y);
  57. if(x != y){
  58. link(x,y);
  59. forests--;
  60. }
  61. return x != y;
  62. }
  63.  
  64.  
  65.  
  66.  
  67.  
  68. };
  69.  
  70. UnionFind uf (1000);
  71. vector<edge> kaursal(int n){
  72.  
  73. vector<edge> edges;
  74. int cost =0;
  75. priority_queue<edge>q;
  76. for(int i=0 ; i<adj.size() ; i++)
  77. q.push(adj[i]);
  78.  
  79. while(!q.empty()){
  80. edge e = q.top();
  81. q.pop();
  82.  
  83. if(uf.union_sets(e.from , e.to)){
  84. cost += e.w;
  85. edges.push_back(e);
  86. }
  87. }
  88.  
  89. return edges;
  90. }
  91.  
  92. double dist(int x1,int x2){
  93. return (arr[x1][0] - arr[x2][0])*(arr[x1][0] - arr[x2][0]) + (arr[x1][1] - arr[x2][1])*(arr[x1][1] - arr[x2][1]);
  94. }
  95.  
  96. int main()
  97. {
  98. int t;
  99. cin >> t;
  100. while(t--){
  101. cin >> n;
  102. uf.reset();
  103. for(int i=0 ; i<n ; i++){
  104. cin >> arr[i][0];
  105. cin >> arr[i][1];
  106. }
  107. int m;
  108. cin >> m ;
  109. for(int i=0 ; i <m ; i++){
  110. int x1,x2;
  111. cin >> x1>>x2;
  112. uf.union_sets(x1-1,x2-1);
  113. }
  114. for(int i=0 ; i<n ; i++){
  115. for(int j=0 ; j<n ; j++){
  116. adj.push_back(edge(i,j,dist(i,j)));
  117. }
  118. }
  119.  
  120. vector<edge> v = kaursal(n);
  121. if(v.size() == 0)cout << "No new highways need";
  122. else{
  123. for(int i=0 ; i<v.size() ; i++){
  124. cout << min(v[i].from+1,v[i].to+1) << " " << max(v[i].from+1,v[i].to+1);
  125. if(i != v.size()-1)cout << endl;
  126. }
  127. }
  128. adj.clear();
  129. }
  130.  
  131. return 0;
  132.  
  133. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement