1821: [JSOI2010]Group 部落劃分 Group

Time Limit: 10 Sec Memory Limit: 64 MB

Description

聰聰研究發現，荒島野人總是過著群居的生活，但是，并不是整個荒島上的所有野人都屬于同一個部落，野人們總是拉幫結派形成屬于自己的部落，不同的部落之間則經常發生爭斗。只是，這一切都成為謎團了——聰聰根本就不知道部落究竟是如何分布的。 不過好消息是，聰聰得到了一份荒島的地圖。地圖上標注了N個野人居住的地點（可以看作是平面上的坐標）。我們知道，同一個部落的野人總是生活在附近。我們把兩個部落的距離，定義為部落中距離最近的那兩個居住點的距離。聰聰還獲得了一個有意義的信息——這些野人總共被分為了K個部落！這真是個好消息。聰聰希望從這些信息里挖掘出所有部落的詳細信息。他正在嘗試這樣一種算法： 對于任意一種部落劃分的方法，都能夠求出兩個部落之間的距離，聰聰希望求出一種部落劃分的方法，使靠得最近的兩個部落盡可能遠離。 例如，下面的左圖表示了一個好的劃分，而右圖則不是。請你編程幫助聰聰解決這個難題。

Input

第一行包含兩個整數N和K(1< = N < = 1000,1< K < = N)，分別代表了野人居住點的數量和部落的數量。
接下來N行，每行包含兩個正整數x,y，描述了一個居住點的坐標(0 < =x, y < =10000)

Output

輸出一行，為最優劃分時，最近的兩個部落的距離，精確到小數點后兩位。

Sample Input

4 2
0 0
0 1
1 1
1 0

Sample Output

1.00

題解

我們有個貪心的想法，是要將小的連起來，最后剩下K個聯通塊，那么我們就需要連n-K條邊，那就直接MST就可以了。

代碼如下

#include<cmath> #include<cstdio> #include<algorithm> using namespace std; int n,K,cnt,fa[1005],costx[1005],costy[1005]; struct xcw{int x,y,w;bool operator <(const xcw b)const{return w<b.w;} }a[1000005]; double get(int i,int j){return (costx[i]-costx[j])*(costx[i]-costx[j])+(costy[i]-costy[j])*(costy[i]-costy[j]);} int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);} int main(){#ifndef ONLINE_JUDGEfreopen("prob.in","r",stdin);freopen("prob.out","w",stdout);#endifscanf("%d%d",&n,&K);for(int i=1;i<=n;i++) fa[i]=i;for(int i=1;i<=n;i++) scanf("%d%d",&costx[i],&costy[i]);for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++) a[++cnt]=(xcw){i,j,get(i,j)};sort(a+1,a+1+cnt);for(int i=1;i<=cnt;i++){int fx=getfa(a[i].x),fy=getfa(a[i].y);if(fx==fy) continue;fa[fy]=fx;n--;if(n<K){printf("%.2lf\n",sqrt(a[i].w));return 0;}}return 0; }

轉載于:https://www.cnblogs.com/XSamsara/p/9030298.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

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

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