歡迎訪問~原文出處——博客園-zhouzhendong

去博客園看該題解

---

題目傳送門 - BZOJ1821

---

題意概括

　　平面上有n個點，現在把他們劃分成k個部分，求不同部分之間最近距離的最大值。

　　兩個部分的距離就是兩個部分中的最近的點對的距離。

?　　n<=1000

---

?

題解

　　我們把所有的點全部建邊。

　　然后我們要更新答案，就要盡量弄掉短的邊。

　　于是就按照kruscal那樣從短的開始弄。

　　當然要用并查集。

　　最后答案就是剩余的有意義的邊中最短的一條。

　　注意最后的處理，我由于這個wa了好多次。

---

?

代碼

#include <cstring> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cmath> using namespace std; const int N=1000+5,M=N*N; int n,k,fa[N]; struct Point{int x,y; }p[N]; int sqr(int x){return x*x; } struct Edge{int a,b,c; }e[M]; bool cmp(Edge a,Edge b){return a.c<b.c; } int getf(int k){return fa[k]==k?k:fa[k]=getf(fa[k]); } int main(){scanf("%d%d",&n,&k);for (int i=1;i<=n;i++)scanf("%d%d",&p[i].x,&p[i].y);int cnt=0;for (int i=1;i<=n;i++)for (int j=i+1;j<=n;j++){e[++cnt].a=i,e[cnt].b=j;e[cnt].c=sqr(p[i].x-p[j].x)+sqr(p[i].y-p[j].y);}sort(e+1,e+cnt+1,cmp);int tot=0;for (int i=1;i<=n;i++)fa[i]=i;int i;for (i=1;i<=cnt&&n-tot>k;i++){int a=e[i].a,b=e[i].b;if (getf(a)==getf(b))continue;fa[getf(a)]=getf(b);tot++;}for (;i<=cnt&&getf(e[i].a)==getf(e[i].b);i++);printf("%.2lf",sqrt(e[i].c));return 0; }

　　

轉載于:https://www.cnblogs.com/zhouzhendong/p/BZOJ1821.html

總結

以上是生活随笔為你收集整理的BZOJ1821 [JSOI2010]Group 部落划分 Group Kruskal的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。