一道最小生成树经典题
由于是最靠近的两个部落尽可能远，如果我们先处理出任意两个居住点之间的距离并将其当做边，那么我们可以发现，因为在一个部落里面的边是不用计入答案的，所以应该要尽量把小边放在一个部落里，
由此，我们可以想到最小生成树，也是每次都优先选小的边，只不过这里要求的是尽可能远，所以就相当于是把选出的最小边都去掉。
那k个集合的问题怎么办呢？
我们在做最小生成树的时候，其实也是集合不断合并的过程，放在这道题中，就相当于是一个个居住点不断被划分到部落里的过程，因此当集合只剩k个时，也就是分配好了k个部落，因为每次合并都会少一个集合，所以我们用一个变量记录下来当前还有多少集合（或还要删几个，已经删了几个之类的都可以）。
剩k个的时候就退出。
然后由于边已经排好序，所以我们从退出的那条边（没有被选上）开始，依次向后遍历，第一个不在一个集合里的边就是答案（因为在一个集合里就意味这被划分到了一个部落，不能算作答案）
简而言之就是：将求最小值最大转换为用kruskal去掉小边，最后就会留下最优的边
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define AC 1000010 4 #define R register int 5 struct abc{ 6 int f,w,length; 7 }way[AC]; 8 int n,k,x[1010],y[1010],now; 9 int father[1010],tot,cnt;//tot为已经消除的并查集个数， 10 11 bool cmp(abc a,abc b) 12 { 13 return a.length<b.length; 14 } 15 16 inline int find(int x) 17 { 18 if(father[x]==x) return x; 19 else return father[x]=find(father[x]); 20 } 21 22 inline int read() 23 { 24 int x=0;char c; 25 while(isspace(c=getchar())); 26 while(c>='0' && c<='9')x=x*10+c-'0',c=getchar(); 27 return x; 28 } 29 30 void kruskal() 31 { 32 int father1,father2; 33 for(R i=1;i<=cnt;i++) 34 { 35 father1=find(way[i].f),father2=find(way[i].w); 36 if(father1!=father2) 37 { 38 tot++; 39 if(father1<father2) father[father2]=father1; 40 else father[father1]=father2; 41 if(n-tot==k)//合并到k个集合就退出 42 { 43 now=i+1;//搜索答案从now开始，因为之前没有选的边都是因为在同一个集合内 44 break;//而这里要统计的是不同部落的距离 45 } 46 } 47 } 48 } 49 50 void pre() 51 { 52 n=read(),k=read(); 53 for(R i=1;i<=n;i++) x[i]=read(),y[i]=read(),father[i]=i; 54 for(R i=1;i<=n;i++) 55 for(R j=i+1;j<=n;j++) 56 { 57 way[++cnt].f=i,way[cnt].w=j; 58 way[cnt].length=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]); 59 }//非真实距离 60 sort(way+1,way+cnt+1,cmp); 61 } 62 63 void work() 64 { 65 kruskal(); 66 for(R i=now;i<=cnt;i++) 67 { 68 if(find(way[i].f) != find(way[i].w)) 69 { 70 printf("%.2f ",sqrt((double)way[i].length)); 71 exit(0); 72 } 73 } 74 } 75 76 int main() 77 { 78 // freopen("in.in","r",stdin); 79 pre(); 80 work(); 81 // fclose(stdin); 82 return 0; 83 }