最小生成树之——已知一条边求最小生成树

题目：hdu4463

题意：已知一条边求最小生成树

题解：用kruskal的话，先将该条边连接。再求最小生成树。

注意：是双向边！

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int n;
int p,q;
bool vis[55][55];
struct point
{
    double x,y;
};
point pp[55];
struct edge
{
    int u;
    int v;
    double w;
};
bool cmp(edge a,edge b)
{
    return a.w < b.w;
}
double cal(point a,point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
struct edge e[5000];
int f[50] = {0},cnt = 0;
double sum = 0;
int getf(int v)
{
    if(f[v] == v)
        return v;
    else
    {
        f[v] = getf(f[v]);
        return f[v];
    }
}
int Merge(int v,int u)
{
    int t1,t2;
    t1 = getf(v);
    t2 = getf(u);
    if(t1 != t2)
    {
        f[t2] = t1;
        return 1;
    }
    return 0;
}
int main()
{
    while(scanf("%d",&n))
    {
        if(n == 0)
            break;
        sum = 0;
        cnt = 0;
        scanf("%d%d",&p,&q);
        p--;
        q--;
        for(int i = 0;i < n;i++)
            scanf("%lf%lf",&pp[i].x,&pp[i].y);
        int tot = 0;
        for(int i = 0;i < n-1;i++)
            for(int j = i+1;j < n;j++)
        {
            e[tot].u = i;
            e[tot].v = j;
            e[tot].w = cal(pp[i],pp[j]);
            tot++;
            e[tot].v = i;
            e[tot].u = j;
            e[tot].w = cal(pp[i],pp[j]);
            tot++;
        }
        sort(e,e+tot,cmp);
        for(int i = 0;i < n;i++)
            f[i] = i;
        Merge(p,q);
        sum += cal(pp[p],pp[q]);
        cnt++;
        for(int i = 0;i < tot;i++)
        {
            if(Merge(e[i].u,e[i].v))
            {
                cnt++;
                sum = sum + e[i].w;
                vis[e[i].u][e[i].v] = 1;
            }
            if(cnt == n-1)
                break;
        }
            printf("%.2f\n",sum);
    }
    return 0;
}

转载自：https://blog.csdn.net/Sleppypot/article/details/52266193