P4047 部落划分 最小生成树

· · 个人记录

n个点，分k份，使靠的最近的两份距离尽可能大

最小的最大，触发二分关键词，倒也可以做

朴素想法：离越近越应该分在一起，至少比不分在一起好

实现的话就类似最小生成树的kruskal算法

需要注意的是，如果简单粗暴地存边，需要把数组开到n方，即1e6

100pts：

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
const int Max=2e4;
struct Edge{
    int u,v;
    double w;
}edge[N];
struct Node{
    int x,y;
}node[N];
int cnt,fa[N];
int n,k;
double Dis(int a,int b){
    return sqrt((node[a].y-node[b].y)*(node[a].y-node[b].y)+
                (node[a].x-node[b].x)*(node[a].x-node[b].x));
}
bool cmp(Edge a,Edge b){return a.w<b.w;}
int find(int a){
    if(fa[a]!=a) return fa[a]=find(fa[a]);
    return fa[a];
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)   scanf("%d%d",&node[i].x,&node[i].y),fa[i]=i;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++){
            edge[++cnt].u=i,edge[cnt].v=j,edge[cnt].w=Dis(i,j);         
        }
    sort(edge+1,edge+1+cnt,cmp);
//  for(int i=1;i<=cnt;i++){
//      printf("(%d,%d):%.2lf\n",edge[i].u,edge[i].v,edge[i].w);
//  }
    int u,v;
    bool flag=false;
    for(int i=1;i<=cnt;i++){
        u=edge[i].u,v=edge[i].v;
        if(find(u)!=find(v)){
            if(flag){
                printf("%.2lf\n",edge[i].w);
                break;
            }
            else{
                n--;
                fa[fa[v]]=find(u);
            }
        }
        if(n==k){
//          printf("QAQ %d\n",i);
//          printf("%.2lf %d",edge[i+1].w,i+1); 非部落间距 
            flag=true;
        }
    }
    return 0;
}