SHARE
TWEET

Untitled

a guest Jun 24th, 2019 62 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 760;
  5.  
  6. int parent[N];
  7. int siz[N];
  8. vector<pair<pair<int,int>,long long> > elist;
  9. vector<pair<int,int> > path[N];
  10.  
  11.  
  12.  
  13. void make_set(int v)
  14. {
  15.     parent[v] = v;
  16.     siz[v] = 1;
  17. }
  18.  
  19. int find_set(int v)
  20. {
  21.     if(v == parent[v])
  22.         return v;
  23.     return parent[v] = find_set(parent[v]);
  24. }
  25.  
  26. void union_set(int a,int b)
  27. {
  28.     a = find_set(a);
  29.     b = find_set(b);
  30.     if(a != b)
  31.     {
  32.         if(siz[a] < siz[b])
  33.             swap(a,b);
  34.         parent[b] = a;
  35.         siz[a] +=siz[b];
  36.         siz[b] = 0;
  37.     }
  38. }
  39. /*int vis[N];
  40. int vid = 1;
  41. int minimum;*/
  42. int highwaycnt = 0;
  43.  
  44. /*void dfs(int idx,int mn,int target)
  45. {
  46.     //printf("%d %d %d\n",idx,mn,target);
  47.     if(idx == target)
  48.     {
  49.         minimum = mn;
  50.         return;
  51.     }
  52.     vis[idx] = vid;
  53.     for(int i = 0; i < path[idx].size(); i++)
  54.         if(vis[path[idx][i].first] != vid)
  55.             dfs(path[idx][i].first,min(mn,path[idx][i].second),target);
  56.     return;
  57. }*/
  58.  
  59. bool cmp(pair<pair<int,int>,long long> a,pair<pair<int,int>,long long> b)
  60. {
  61.     return a.second < b.second;
  62. }
  63.  
  64. //bool flag = false;
  65.  
  66. void mst()
  67. {
  68.    sort(elist.begin(),elist.end(),cmp);
  69.    for(int i = 0; i < elist.size(); i++)
  70.    {
  71.        int u = elist[i].first.first,v = elist[i].first.second;
  72.        //int cost = elist[i].second;
  73.        /*if(u == 1 && v == 6)
  74.         printf("1 %I64d\n",elist[i].second);
  75.        if(u == 2 && v == 8)
  76.         printf("2 %I64d\n",elist[i].second);*/
  77.        if(find_set(u) != find_set(v))
  78.        {
  79.            union_set(u,v);
  80.            printf("%d %d\n",u,v);
  81.            highwaycnt++;
  82.            //path[u].push_back(make_pair(v,cost));
  83.            //path[v].push_back(make_pair(u,cost));
  84.        }
  85.    }
  86.    return;
  87. }
  88.  
  89. void init()
  90. {
  91.     for(int i = 0; i < N; i++)
  92.         make_set(i);
  93.     elist.clear();
  94.     //flag = false;
  95.     highwaycnt = 0;
  96.     //for(int i = 0; i < N; i++)
  97.       //  path[i].clear();
  98.     //memset(vis,0,sizeof vis);
  99. }
  100.  
  101. long long calc(int x1,int y1, int x2,int y2)
  102. {
  103.     return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
  104. }
  105.  
  106. bool cmp2(int i, int j)
  107. {
  108.     return i > j;
  109. }
  110.  
  111. int t;
  112. int n,m;
  113. int x,y;
  114.  
  115. map<int,pair<int,int> > cities;
  116.  
  117. int main()
  118. {
  119.     ios::sync_with_stdio(0);
  120.     cin.tie(NULL);
  121.     cout.tie(NULL);
  122.  
  123.     #ifndef ONLINE_JUDGE
  124.         //freopen("input.txt", "r", stdin);
  125.         //freopen("out.txt", "w", stdout);
  126.     #endif // ONLINE_JUDGE
  127.  
  128.     scanf("%d",&t);
  129.     while(t--)
  130.     {
  131.         init();
  132.         scanf("%d",&n);
  133.         int cnt = 1;
  134.         for(int i = 0; i < n; i++)
  135.         {
  136.             scanf("%d%d",&x,&y);
  137.             cities[cnt++] = {x,y};
  138.         }
  139.         for(map<int,pair<int,int> >::iterator it1 = cities.begin(); it1 != cities.end();it1++)
  140.             for(map<int,pair<int,int> >::iterator it2 = cities.begin(); it2 != cities.end(); it2++)
  141.                 if(it1->first < it2->first)
  142.                     elist.push_back(make_pair(make_pair(it1->first,it2->first),calc(it1->second.first,it1->second.second,it2->second.first,it2->second.second)));
  143.         scanf("%d",&m);
  144.         for(int i = 0; i < m; i++)
  145.         {
  146.             scanf("%d%d",&x,&y);
  147.             union_set(x,y);
  148.         }
  149.         if(highwaycnt == n-1)
  150.             puts("No new highways need");
  151.         else
  152.             mst();
  153.         //printf("%I64d",calc(1,5))
  154.         if(t)
  155.             puts("");
  156.     }
  157.  
  158.     return 0;
  159. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top