求包含給定的M條邊的最小生成樹。

可以用Kruskal算法加並查集，再讀入M條邊的時候先把這些邊加入樹中，再把最小的不構成環的N(N-1)/2-1-M條邊加入樹，算出邊權和。

//最小生成樹 Kruskal + 並查集
#include <iostream>
#include <cmath>
#define MAX 1001
using namespace std;

class tUFS
{
private:
    int F[MAX],Size;
    int findroot(int a)
    {
        int b=a,t;
        while (F[a]>0)
            a=F[a];
        while (F[b]>0)
        {
            t=F[b];
            F[b]=a;
            b=t;
        }
        return a;
    }
public:
    bool judge(int a,int b)
    {
        return F[findroot(a)]==F[findroot(b)];
    }
    void merge(int a,int b)
    {
        F[findroot(b)]=findroot(a);
    }
    tUFS(int N)
    {
        Size=N;
        for (int i=1;i<=N;i++)
            F[i]=-i;
    }
};

typedef struct
{
    int a,b;
    double v;
}edge;

typedef struct
{
    int x,y;
}point;

tUFS *U;
int N,M,C;
double Ans;
edge E[MAX*MAX];
point P[MAX];

void quicksort(int i,int j)
{
    int t1=i,t2=j;
    edge T,k=E[(i+j)/2];
    do
    {
        while (E[t1].v<k.v) t1++;
        while (E[t2].v>k.v) t2--;
        if (t1<=t2)
        {
            T=E[t1];
            E[t1]=E[t2];
            E[t2]=T;

            t1++;
            t2--;
        }
    }while (t1<t2);
    if (t2>i) quicksort(i,t2);
    if (t1<j) quicksort(t1,j);
}

inline double dist(point a,point b)
{
    return sqrt ( (double)(a.x-b.x)*(a.x-b.x) + (double)(a.y-b.y)*(a.y-b.y) );
}

void init()
{
    int i,j,a,b;
    freopen("roads.in","r",stdin);
    freopen("roads.out","w",stdout);
    scanf("%d%d",&N,&M);
    U=new tUFS(N);
    for (i=1;i<=N;i++)
        scanf("%d%d",&P[i].x,&P[i].y);
    for (i=1;i<=M;i++)
    {
        scanf("%d%d",&a,&b);
        if (!U->judge(a,b))
            U->merge(a,b);
    }
    for (i=C=1;i<=N-1;i++)
    {
        for (j=i+1;j<=N;j++,C++)
        {
            if (C==62375)
                C=C;
            E[C].a=i;
            E[C].b=j;
            E[C].v=dist(P[i],P[j]);
        }
    }
    C--;
    quicksort(1,C);
}

void kruskal()
{
    int i,cnt;
    for (i=1,cnt=0;i<=C && cnt<C-1-M;i++)
    {
        if (!U->judge(E[i].a,E[i].b))
        {
            U->merge(E[i].a,E[i].b);
            Ans+=E[i].v;
            cnt++;
        }
    }
}

int main()
{
    init();
    kruskal();
    printf("%.2lfn",Ans);
    return 0;
}

<a href="http://www.ruvtex.cn/wiki/USACOMonthly/2007_12_S/Building_Roads/Chinese">建造路徑</a>

譯 by CmYkRgB123

描述

Farmer John 剛剛得到了幾個新農場！他想把這幾個農場用路連接起來，這樣他就可以通過筆直的公路從一個農場到另一個農場了。現在已經有了幾條連接着的農場。

N (1 ≤ N ≤ 1,000) 個農場中，每個農場的位置在座標平面的 (Xi, Yi) (0 ≤ Xi ≤ 1,000,000; 0 ≤ Yi ≤ 1,000,000)。已經有 M (1 ≤ M ≤ 1,000) 條路以前就被建好了。請你幫助 Farmer John 考慮建設儘量少長度的額外的路，使他的農場連在一起。

輸入

    * 第 1 行: 兩個整數: N , M
    * 第 2..N+1 行: 兩個整數 Xi , Yi
    * 第 N+2..N+M+2 行: 兩個整數: i , j, 表示已經存在從農場i到農場j的路。 

輸出

    * 第 1 行: 額外的路的最少長度，保留2小數。 請使用 64 位的浮點數。 

樣例輸入

4 1
1 1
3 1
2 3
4 3
1 4

樣例輸出

4.00