poj2349Arctic Network(最小生成树kruscal+第k长的边）

题目链接：

题意：
北极的某区域共有n座村庄( 1 ≤ n ≤ 500 )，每座村庄的坐标用一对整数(x, y)表示，其中 0 ≤ x, y ≤ 10000。为了加强联系，决定在村庄之间建立通讯网络。通讯工具可以是无线电收发机，也可以是卫星设备。所有的村庄都可以拥有一部无线电收发机， 且所有的无线电收发机型号相同。但卫星设备数量有限，只能给一部分村庄配备卫星设备。  不同型号的无线电收发机有一个不同的参数d，两座村庄之间的距离如果不超过d就可以用该型号的无线电收发机直接通讯，d值越大的型号价格越贵。拥有卫星设备的两座村庄无论相距多远都可以直接通讯。

这道题目主要是那卫星不好处理，但是如果正面不好想，那么可以从逆向来想，如果知道了最小距离D，那么去掉最小生成树里面大于D的边，那么图会存在k个连通支，这里给一个定理：如果去掉所有权大于d的边后最小生成树被分割成k个连通分支，图也被分割成k个连通分支，。那么给每个连通支分一个卫星电话即可，那么这个最短距离D就变成了去掉大于D后的最大的边，即第k长的边。。。。那么这个问题就解决了。。。

题目：

1
2 4
0 100
0 300
0 600
150 750

212.13

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;

const int maxn=500+10;
int s,p,root[maxn],cal;
double dis[maxn*maxn];

struct Point
{
    int x,y;
}point[maxn];

struct Edge
{
    int u,v;
    double distance;
}edge[maxn*maxn];

int findroot(int x)
{
    if(root[x]!=x)
        root[x]=findroot(root[x]);
    return root[x];
}

double caldistance(Point a,Point b)
{
    return sqrt(1.0*(a.x-b.x)*(a.x-b.x)+1.0*(a.y-b.y)*(a.y-b.y));
}


bool cmp(Edge a,Edge b)
{
    return a.distance<b.distance;
}

bool cmp2(double a,double b)
{
    return a>b;
}

void kruscal()
{
    memset(dis,0.0,sizeof(dis));
    int sum=0,i,k=0;
    for(i=1;i<=cal;i++)
    {
        int fx=findroot(edge[i].u);
        int fy=findroot(edge[i].v);
        if(fx==fy)
            continue;
        else
        {
            root[fx]=fy;
            sum++;
            dis[sum]=edge[i].distance;
            if(sum==p-1)
                break;
        }
    }
    sort(dis+1,dis+1+sum,cmp2);
    printf("%.2f\n",dis[s]);
}


void read_graph()
{
    for(int i=1;i<=p;i++)
        root[i]=i;
    for(int i=1;i<=p;i++)
       scanf("%d%d",&point[i].x,&point[i].y);
    for(int i=1;i<p;i++)
       for(int j=i+1;j<=p;+j++)
    {
        double temp=caldistance(point[i],point[j]);
        edge[++cal].u=i;
        edge[cal].v=j;
        edge[cal].distance=temp;
    }
    sort(edge+1,edge+1+cal,cmp);
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        cal=0;
        scanf("%d%d",&s,&p);
        read_graph();
        kruscal();
    }
    return 0;
}

poj2349Arctic Network(最小生成树kruscal+第k长的边）,布布扣,bubuko.com

poj2349Arctic Network(最小生成树kruscal+第k长的边）

原文：http://blog.csdn.net/u014303647/article/details/38487123