Outlets

4
2 3
0 0
1 0
0 -1 
1 -1
0

3.41

题意：

有n家店，要你把他们连在一起（即建成一颗最小生成树），q,p是要求必须有边直接连的，然后就给你n个店的坐标。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<set>
#include<queue>
#include<stack>
#include<vector>
#include<map>

#define N 110
#define Mod 10000007
#define lson l,mid,idx<<1
#define rson mid+1,r,idx<<1|1
#define lc idx<<1
#define rc idx<<1|1
const double EPS = 1e-11;
const double PI = acos ( -1.0 );
typedef long long ll;

const int INF = 1000010;

using namespace std;

int n;
int A,B;
int par[N],R[N];
double X[N],Y[N];
struct edge {
    int u,v;
    double cost;
};

edge es[N*N];
int E;

void init() {
    for(int i=0; i<=n; i++) {
        par[i]=i;
        R[i]=0;
    }
}

int finds(int x) {
    if(par[x]==x)return x;
    return par[x]=finds(par[x]);
}

void unite(int x,int y) {
    x=finds(x);
    y=finds(y);
    if(x==y)return;
    if(R[x]<R[y])par[x]=y;
    else {
        par[y]=x;
        if(R[x]==R[y])R[x]++;
    }
}

bool same(int x,int y) {
    return finds(x)==finds(y);
}

double dis(int i,int j) {
    return sqrt((X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j]));
}

bool cmp(edge a,edge b) {
    return a.cost<b.cost;
}

void kruscal() {
    double ans=dis(A,B);
    unite(A,B);
    for(int i=0; i<E; i++) {
        edge e=es[i];
        if(!same(e.u,e.v)) {
            ans+=e.cost;
            unite(e.u,e.v);
        }
    }
    printf("%.2f\n",ans);
}

int main() {
    while(cin>>n&&n) {
        cin>>A>>B;
        for(int i=1; i<=n; i++)
            cin>>X[i]>>Y[i];
        E=0;
        for(int i=1; i<=n; i++) {
            for(int j=i+1; j<=n; j++) {
                es[E].u=i;
                es[E].v=j;
                es[E++].cost=dis(i,j);
            }
        }
        init();
        sort(es,es+E,cmp);
        kruscal();
    }
    return 0;
}

hdu 4463 Outlets(最小生成树)

原文：http://blog.csdn.net/acm_baihuzi/article/details/44550681