BZOJ1821 部落划分[最小生成树]

方法一：套路性的，二分距离，然后把距离点对距离小于答案的边都联通起来，然后看集合数量超过k说明答案小，增大，否则减小。

方法二：贪心，类kruskal。n个点，k个连通块，则需要有效连接（同一个块内的点相互连接不算）n-k次。那么用类似kruskal的证明过程发现最小的边一定要联通使得集合与集合间距离尽量大，连完n-k条边之后的第n-k+1条连接不同连通块的点对距离即为所求。

code是我一年前写的，现在我只能想出第一种方法，越学越退步，自闭嘤嘤嘤。

 //注：原来代码被我想复杂了，自己对比。

 #include<bits/stdc++.h>

 using namespace std;

 typedef double db;

 const int N=+;

 inline int read(){

     int x=,f=;char ch;

     while(!isdigit(ch=getchar()))if(ch=='-') f=;

     while(isdigit(ch)) x=(x<<)+(x<<)+(ch^''),ch=getchar();

     return f?-x:x;

 }

 struct edge{

     int u,v;db dis;

 }e[N*N];

 int X[N],Y[N],f[N];

 int n,k,m,cnt;

 bool cmp(edge a,edge b){return a.dis<b.dis;}

 int Find(int x){if(f[x]!=x) f[x]=Find(f[x]);return f[x];}

 int main(){

     n=read(),k=read();

     for(register int i=;i<=n;++i){

         X[i]=read(),Y[i]=read();f[i]=i;

         for(register int j=;j<i;++j) e[++m].dis=sqrt((Y[i]-Y[j])*(Y[i]-Y[j])+(X[i]-X[j])*(X[i]-X[j])),e[m].u=i,e[m].v=j;

     }

     sort(e+,e+m+,cmp);

     for(register int i=;i<=m;++i){

         int fx=Find(e[i].u),fy=Find(e[i].v);

         if(fx!=fy){

             f[fy]=fx,++cnt;

             if(cnt==n-k+){printf("%.2f\n",e[i].dis);return ;}

         }

     }

     return ;

 }

巴特西

BZOJ1821 部落划分[最小生成树]

最新文章

热门文章