SHARE
TWEET

UltramanMK3 PROG1115

SuitNdtie Apr 24th, 2019 82 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<stdio.h>
  2. #include<queue>
  3. using namespace std;
  4.  
  5. struct pos{
  6.     int I,J;
  7. };
  8.  
  9. struct edge{
  10.     int u;
  11.     int v;
  12.     int w;
  13.     bool operator < (const edge& rhs)const
  14.     {
  15.         return w > rhs.w;
  16.     }
  17. };
  18.  
  19. int dist(pos x,pos y){
  20.     return ((x.I - y.I)*(x.I - y.I))+((x.J - y.J)*(x.J - y.J));
  21. }
  22.  
  23. int parent[1010];
  24.  
  25. int find(int x){
  26.     if(x == parent[x]){
  27.         return x;
  28.     }
  29.     return parent[x] = find(parent[x]);
  30. }
  31.  
  32. void unions(int x,int y){
  33.     int rx = find(x);
  34.     int ry = find(y);
  35.     parent[rx] = ry;
  36. }
  37.  
  38. int main()
  39. {
  40.     for(int i = 0 ; i < 1010 ; i++)parent[i] = i;
  41.     int n,k;
  42.     scanf("%d %d",&n,&k);
  43.     priority_queue<edge> pq;
  44.     pos house[n];
  45.     for(int i = 0 ; i < n ; i++){
  46.         scanf("%d %d",&house[i].I,&house[i].J);
  47.         for(int j = i - 1 ; j >= 0 ; j --){
  48.             pq.push({i,j,dist(house[i],house[j])});
  49.         }
  50.     }
  51. /*  if(n == k){
  52.         printf("0");
  53.         return 0;
  54.     }*/
  55. //  vector<int> dist;
  56.     int ans = 0;
  57.     int cnt = 0;
  58.     while(!pq.empty() && cnt < n - k){
  59.         int u = pq.top().u;
  60.         int v = pq.top().v;
  61.         int w = pq.top().w;
  62.     //  printf("%d\n",pq.top().w);
  63.         pq.pop();
  64.         if(find(u) != find(v)){
  65.             cnt++;
  66.             unions(u,v);
  67.         //  dist.push_back(w);
  68.             ans = w;
  69.         }
  70.     }
  71. //  printf("%d",dist[dist.size() - k]);
  72.     printf("%d",ans);
  73.     return 0;  
  74. }
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