Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <bits/stdc++.h>
- using namespace std;
- int arr[10009][2];
- int n;
- struct edge{
- int from,to;
- double w;
- edge(int from,int to,double w):from(from),to(to),w(w){}
- bool operator < (const edge &e) const{
- return w > e.w;
- }
- };
- vector<edge>adj;
- struct UnionFind{
- vector<int> parent;
- vector<int> rank;
- int forests;
- UnionFind(int n){
- parent.resize(n);
- rank.resize(n);
- forests =n;
- for(int i=0 ; i<n ; i++){
- parent[i] = i;
- rank[i] =1;
- }
- }
- void reset(){
- for(int i=0 ; i<n ; i++){
- parent[i] = i;
- rank[i] =1;
- }
- forests =n;
- }
- int find_set(int x){
- if(x==parent[x])return x;
- else parent[x] = find_set(parent[x]);
- }
- void link (int x , int y){
- if(rank[x] > rank[y]){
- int tmp =x;
- x = y;
- y = tmp;
- }
- parent[x] = y;
- if(rank[x] == rank[y])rank[y]++;
- }
- bool union_sets(int x , int y){
- x = find_set(x);
- y = find_set(y);
- if(x != y){
- link(x,y);
- forests--;
- }
- return x != y;
- }
- };
- UnionFind uf (1000);
- vector<edge> kaursal(int n){
- vector<edge> edges;
- int cost =0;
- priority_queue<edge>q;
- for(int i=0 ; i<adj.size() ; i++)
- q.push(adj[i]);
- while(!q.empty()){
- edge e = q.top();
- q.pop();
- if(uf.union_sets(e.from , e.to)){
- cost += e.w;
- edges.push_back(e);
- }
- }
- return edges;
- }
- double dist(int x1,int x2){
- 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]);
- }
- int main()
- {
- int t;
- cin >> t;
- while(t--){
- cin >> n;
- uf.reset();
- for(int i=0 ; i<n ; i++){
- cin >> arr[i][0];
- cin >> arr[i][1];
- }
- int m;
- cin >> m ;
- for(int i=0 ; i <m ; i++){
- int x1,x2;
- cin >> x1>>x2;
- uf.union_sets(x1-1,x2-1);
- }
- for(int i=0 ; i<n ; i++){
- for(int j=0 ; j<n ; j++){
- adj.push_back(edge(i,j,dist(i,j)));
- }
- }
- vector<edge> v = kaursal(n);
- if(v.size() == 0)cout << "No new highways need";
- else{
- for(int i=0 ; i<v.size() ; i++){
- cout << min(v[i].from+1,v[i].to+1) << " " << max(v[i].from+1,v[i].to+1);
- if(i != v.size()-1)cout << endl;
- }
- }
- adj.clear();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement