Luogu p4047 [jsoi2010] tribal division solution

Luogu P4047 [JSOI2010] Tribal Division Answer key

Topic link ：P4047 [JSOI2010] Tribal Division

The question ：

Congcong's research found that , Wild islanders always live in groups , however , Not all the savages on the whole desert island belong to the same tribe , Wild people are always ganging up to form their own tribes , There are often fights between different tribes . It's just , It's all a mystery —— Congcong doesn't know how the tribes are distributed .

But the good news is , Congcong gets a map of the desert island . The map is marked $n$ A place where savages live （ It can be regarded as coordinates on the plane ）. We know , Savages of the same tribe always live nearby . We put the distance between the two tribes , It is defined as the distance between the two nearest settlements in the tribe . Congcong also got a meaningful message —— These savages are divided into $k$ Tribes ！ That's good news . Congcong hopes to mine the details of all tribes from this information . He is trying such an algorithm ：

For any method of tribal division , Can find the distance between the two tribes , Congcong hopes to find a way to divide tribes , Keep the two nearest tribes as far away as possible .

for example , The left figure below shows a good division , The picture on the right is not . Please program to help Congcong solve this problem .

about $100\%$ The data of , Guarantee $2\le k\le n\le 10^3$,$0\le x,y\le 10^4$.

The minimum distance is the maximum , One eye and two points

But here is a kruskal Solution method

Let's put the $O(n^2)$ The edge is built

Then find the minimum spanning tree

Greedily divide the minimum spanning tree into $k$ A connecting block

Concrete , We just merge the smallest edges of the tree in turn

Finally, a total of $(n-1)-(k-1)=n-k$ side

So the answer is $n-k+1$ The edge weight of the edge

Mouth paste a proof of correctness （ Maybe not very rigorous ）

Consider counter evidence

Set an edge on the minimum spanning tree $w_1(u,v)$ , Replace it with $w_2(u,v^{\prime })$ （$w_2>w_1$）

• If $w_1$ Will be merged and we merged $w_2$ , It seems that there is no change

• If $w_1$ Will be merged and we didn't merge $w_2$ ,

  Then we must merge a ratio $w_1$ Big side , And it is the edge on the minimum spanning tree

  So the answer will be too big

• If $w_1$ Will not be merged and we merged $w_2$ , There is no such situation .

• If $w_1$ Will not be merged and we did not merge $w_2$ , No influence .

Time complexity $O(n^2\log n)$

Code ：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e3+15)
#define M (int)(1e6+15)
#define pf(x) ((x)*(x))
struct Edge{
    int u,v,w;}e[M];
int n,k,f[N],x[N],y[N],c[N],pos;
int find(int x){
    return f[x]==x?x:f[x]=find(f[x]);}
void merge(int u,int v){
    f[find(u)]=find(v);}
void addEdge(int u,int v,int w){
    e[++pos]={
    u,v,w};}
int dis(int i,int j){
    return pf(x[i]-x[j])+pf(y[i]-y[j]);}
void kruskal()
{
    
    sort(e+1,e+1+pos,[](Edge a,Edge b)
    {
    
        return a.w<b.w;
    });
    int cnt=0;
    for(int i=1; i<=pos&&cnt<n; i++)
    {
    
        int u=e[i].u,v=e[i].v;
        if(find(u)!=find(v))
        {
    
            merge(u,v);
            c[++cnt]=e[i].w;
        }
    }
}
signed main()
{
    
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> k;
    for(int i=1; i<=n; i++)
        f[i]=i,cin >> x[i] >> y[i];
    for(int i=1; i<=n; i++)
        for(int j=1; j<i; j++)
            addEdge(i,j,dis(i,j));
    kruskal();
    cout << fixed << setprecision(2);
    cout << sqrt((double)c[n-k+1]) << '\n';
    return 0;
}

Reprint please explain the source