POJ2349&ZOJ1914--Arctic Network【最小生成树】

链接：http://poj.org/problem?id=2349

题意：北极有一些村庄，现需要在这些村庄间建立起通讯，有s个卫星频道，任何两个拥有卫星频道的村庄都可以直接通过卫星进行通讯而无视距离，没有卫星的村庄通过无线电进行通讯，并且这两个村庄的距离不能超过D，D值取决于无线电收发器的功率，功率越大，D值越大，但价格也越高，出于购买费用和维护费用的考虑，所有村庄的无线电收发器都相同，即D值相同，现要求在保证任意两个村庄间都能直接或间接通讯，并且D值最小，输出这个最小值。

就是输出最小生成树最大边的权值，但是卫星频道是不确定因素。这道题有个很好的解法及证明。

以下大号字摘自IOI2004国家集训队论文《最小生成树算法及其应用》（吴景岳）：

当正向思考受阻时， 逆向思维可能有奇效。 本题就是这样。 知道卫星设备的数量，求最小的收发距离，可能比较困难；如果知道距离求数量，就很简单了。把所有可以互相通讯的村庄连接起来， 构成一个图。 卫星设备的台数就是图的连通支的个数。
问题转化为：找到一个最小的 d，使得把所有权值大于 d 的边去掉之后，连通支的个数小于等于 k。
先看一个定理。 定理 2： 如果去掉所有权值大于 d 的边后， 最小生成树被分割成为 k 个连通支，图也被分割成为 k 个连通支。
证明：
用反证法。假设原图被分割成 k’   (k‘≠k)个连通支，显然不可能 k’>k，所以k’<k。 因此在某一图的连通支中， 最小生成树被分成了至少两部分， 不妨设其为T1,T2。因为 T1 和 T2 同属于一个连通支，所以一定存在 x∈T1，y∈T2，w(x, y)≤d。又因为在整个最小生成树中，所以 x 到 y 的路径中一定存在一条权值大于d 的边(u,v) （否则 x 和 y 就不会分属于 T1 和 T2 了） ， w(x, y)≤d<w(u,v)， 所以把(x, y)加入，把(u,v)去掉，将得到一棵总权值比最小生成树还小的生成树。这显然是不可能的。所以，原命题成立。 （证毕）
有了这个定理， 很容易得到一个构造算法： 最小生成树的第 k 长边就是问题的解。
证明：
首先，d 取最小生成树中第 k 长的边是可行的。如果 d 取第 k 长的边，我们将去掉最小生成树中前 k-1 长的边， 最小生成树将被分割成为 k 部分。 由定理 2，原图也将分割成为 k 部分。 （可行性）
其次， 如果 d 比最小生成树中第 k 长的边小的话， 最小生成树至少被分割成为 k+1 部分，原图也至少被分割成为 k+1 部分。与题意不符。 （最优性）
综上所述，最小生成树中第 k 长的边是使得连通支个数≤k 的最小的 d，即问题的解。 （证毕）

s为卫星频道数量，输出最小生成树的第s大边就行了，s为0的时候情况和1一样，卫星都不起作用（两个才能相互通讯），需要特判输出第一大的边，不过题目中不会给s为0的情况，我就没有特判

#include<cstring>
#include<string>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<ctime>
#include<cstdlib>
#include<functional>
#include<cmath>
using namespace std;
#define PI acos(-1.0)
#define MAXN 1000010
#define eps 1e-7
#define INF 0x7FFFFFFF
#define seed 131
#define ll long long
#define ull unsigned ll
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

struct node{
    int u,v;
    double dis;
}edge[MAXN];
int father[550];
int n,m,cnt,s;
double x[550],y[550];
double ans[550];
bool cmp(node x,node y){
    return x.dis<y.dis;
}
int find(int x){
    int t = x;
    while(father[t]!=t){
        t = father[t];
    }
    int k = x;
    while(k!=t){
        int temp = father[k];
        father[k] = t;
        k = temp;
    }
    return t;
}
void kruskal(){
    int i,j=0;
    for(i=1;i<=n;i++)   father[i] = i;
    for(i=0;i<m;i++){
        int a = find(edge[i].u);
        int b = find(edge[i].v);
        if(a!=b){
            father[a] = b;
            ans[cnt++] = edge[i].dis;
            j++;
            if(j>=n-1)  break;
        }
    }
}
int main(){
    int t,i,j,a,b;
    scanf("%d",&t);
    while(t--){
        cnt = 0;
        m = 0;
        scanf("%d%d",&s,&n);
        for(i=1;i<=n;i++){
            scanf("%lf%lf",&x[i],&y[i]);
            for(j=1;j<i;j++){
                edge[m].u = i;
                edge[m].v = j;
                double temp = (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
                edge[m].dis = sqrt(temp);
                m++;
            }
        }
        sort(edge,edge+m,cmp);
        kruskal();
        printf("%.2f\n",ans[cnt-s]);
    }
    return 0;
}

POJ2349&ZOJ1914--Arctic Network【最小生成树】,古老的榕树,5-wow.com