POJ_2349_Arctic Network(最小生成树)

Description

Input

Output

Sample Input

1
2 4
0 100
0 300
0 600
150 750

Sample Output

212.13

题意：这题是上acm课的时候老师布置的一道题，题意反正我是看很久没看懂。大概就是求最小生成树的第k大边，于是，就是裸题了。

分析：kruskal算法求最小生成树。第k大边，也就是第(n-k)小边，所以跑kruskal的时候到(n-k)条边时，直接输出边的权值即可。对了，该题在POJ上交的时候g++一直wa，然后改成c++才ac的。关于这点，我也是不清楚为什么，若有大神经过，望指点迷津。

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

代码清单：

#include<map>
#include<cmath>
#include<queue>
#include<stack>
#include<ctime>
#include<cctype>
#include<string>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;

const int maxn = 500 + 5;

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

struct Point{
    double x;
    double y;
}point[maxn];

int father[maxn];
int t,s,p,cnt,sum;

void init(){
    cnt=0;
    sum=0;
    for(int i=0;i<maxn;i++) father[i]=i;
}

void input(){
    scanf("%d%d",&s,&p);
    for(int i=0;i<p;i++)
        scanf("%lf%lf",&point[i].x,&point[i].y);
}

double Dis(Point p1,Point p2){  //求两点距离
    return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}

bool cmp(Edge a,Edge b){ return a.dis<b.dis; } //边按从小到大排序

int Find(int x){             //并查集压缩路径
    if(x!=father[x]) return father[x]=Find(father[x]);
    return father[x];
}

void solve(){
    for(int i=0;i<p-1;i++){
        for(int j=i+1;j<p;j++){
            edge[cnt].u=i;
            edge[cnt].v=j;
            edge[cnt++].dis=Dis(point[i],point[j]);
        }
    }
    sort(edge,edge+cnt,cmp);
    for(int i=0;i<cnt;i++){
        int uu=Find(edge[i].u);
        int vv=Find(edge[i].v);
        if(uu!=vv){
            sum++;
            father[vv]=uu;
            if(sum+s==p){
                printf("%.2lf\n",edge[i].dis);
                break;
            }
        }
    }
}

int main(){
    scanf("%d",&t);
    while(t--){
        init();
        input();
        solve();
    }return 0;
}