[JSOI2010]部落划分

嘟嘟嘟

一道不错的题，解法不少。

最易于理解的是最小生成树的做法：

首先每两个点之间都连一条长度为这两个点的距离的边，形成完全图。

然后跑最小生成树，直到剩k个联通块，这时候合并成k - 1个联通块的边的长度就是答案（注意，是连接两个联通块的边，否则就不是部落间的距离了）。

正确性很显然。因为这保证了部落内的距离尽量小，则部落外的距离尽量大，所以靠的最近的两个部落也就尽可能的远离。

还有一种二分答案的方法：

每一次把距离小于mid的点都划分成一个部落，最后看形成的部落总数和k的关系，如果小于k，向左二分；否则向右二分。

时间复杂度都是O(ElogE)，E为边数，等于n * (n - 1) / 2。(最小生成树算法排序时间O(ElogE)，跑kruskal时时O(E)的)

方法一的代码

 #include<cstdio>

 #include<iostream>

 #include<cmath>

 #include<algorithm>

 #include<cstring>

 #include<cstdlib>

 #include<cctype>

 #include<vector>

 #include<stack>

 #include<queue>

 using namespace std;

 #define enter puts("")

 #define space putchar(' ')

 #define Mem(a, x) memset(a, x, sizeof(a))

 #define rg register

 typedef long long ll;

 typedef double db;

 const int INF = 0x3f3f3f3f;

 const db eps = 1e-;

 const int maxn = 1e3 + ;

 const int maxe = 5e5 + ;

 inline ll read()

 {

     ll ans = ;

     char ch = getchar(), last = ' ';

     while(!isdigit(ch)) {last = ch; ch = getchar();}

     while(isdigit(ch)) {ans = ans *  + ch - ''; ch = getchar();}

     if(last == '-') ans = -ans;

     return ans;

 }

 inline void write(ll x)

 {

     if(x < ) x = -x, putchar('-');

     if(x >= ) write(x / );

     putchar(x %  + '');

 }

 int n, k;

 struct Node

 {

     int x, y;

 }a[maxn];

 struct Edge

 {

     int x, y; ll c;

     bool operator < (const Edge &oth)const

     {

         return c < oth.c;

     }

 }e[maxe];

 int ecnt = ;

 ll calc(Node a, Node b)

 {

     return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);

 }

 int p[maxn];

 void init()

 {

     for(int i = ; i <= n; ++i) p[i] = i;

 }

 int Find(int x)

 {

     return x == p[x] ? x : p[x] = Find(p[x]);

 }

 int main()

 {

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

     init();

     for(int i = ; i <= n; ++i) a[i].x = read(), a[i].y = read();

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

         for(int j = i + ; j <= n; ++j)

             e[++ecnt] = (Edge){i, j, calc(a[i], a[j])};

     sort(e + , e + ecnt + );

     int cnt = n;

     for(int i = ; i <= ecnt; ++i)

     {

         int px = Find(e[i].x), py = Find(e[i].y);

         if(px != py)

         {

             if(cnt-- == k) {printf("%.2lf\n", sqrt(e[i].c)); return ;}

             p[px] = py;

         }

     }

     return ;

 }

巴特西

[JSOI2010]部落划分

最新文章

热门文章