HDU 1875 畅通工程再续

最小生成树

最小生成树是一副连通加权无向图中一棵权值最小的生成树

主要可以使用Prim和Kruskal算法(借助并查集)实现

稠密图、点少边多：Prim

稀疏图、边多点少：Kruskal

Kruskal算法

对所有权值进行从小到大排序

然后每次选取最小的权值，如果和已有点集构成环则跳过，否则加到该点集中。

Prim算法

将一个图分为两部分，一部分归为点集U，一部分归为点集V，U的初始集合为{V1}，V的初始集合为{ALL-V1}。

针对U开始找U中各节点的所有关联的边的权值最小的那个，然后将关联的节点Vi加入到U中，并且从V中删除（注意不能形成环）。

递归执行步骤2，直到V中的集合为空。

Description

相信大家都听说一个“百岛湖”的地方吧，百岛湖的居民生活在不同的小岛中，当他们想去其他的小岛时都要通过划小船来实现。现在政府决定大力发展百岛湖，发展首先要解决的问题当然是交通问题，政府决定实现百岛湖的全畅通！经过考察小组RPRush对百岛湖的情况充分了解后，决定在符合条件的小岛间建上桥，所谓符合条件，就是2个小岛之间的距离不能小于10米，也不能大于1000米。当然，为了节省资金，只要求实现任意2个小岛之间有路通即可。其中桥的价格为 100元/米。

Input

输入包括多组数据。输入首先包括一个整数T(T <= 200)，代表有T组数据。每组数据首先是一个整数C(C <= 100),代表小岛的个数，接下来是C组坐标，代表每个小岛的坐标，这些坐标都是 0 <= x, y <= 1000的整数。

Output

每组输入数据输出一行，代表建桥的最小花费，结果保留一位小数。如果无法实现工程以达到全部畅通，输出”oh!”.

Sample Input

Sample Output

1414.2

oh!

Code of Kruskal

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 125;

int n;
double ans;
int pre[N];
double x[N], y[N];

struct node
{
    int there, here;
    double w;
} a[10005];

bool cmp(node a, node b)
{
    return a.w < b.w;
}

void init()
{
    ans = 0;
    for(int i = 0; i <= n; ++i)///初始化顶级是自身
        pre[i] = i;
}

//int found(int x)
//{
//    if(x == pre[x])///顶级是自身
//        return x;
//    return found(pre[x]);///一级一级地向上找至找到顶级
//}

int found(int x)
{
    if(x != pre[x])///顶级是自身
        pre[x] = found(pre[x]);
    return pre[x];///压缩路径
}

bool judge(int a, int b)
{
    int x = found(a);
    int y = found(b);
    if(x != y)
    {
        pre[x] = y;
        return 1;
    }
    return 0;
}

int main()
{
    int t;
//    freopen("00in.txt", "r", stdin);
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        init();
        for(int i = 0; i < n; ++i)
            scanf("%lf%lf", &x[i], &y[i]);
        int tot = 0;
        double dis;
        for(int i = 0; i < n - 1; ++i)
            for(int j = i + 1; j < n; ++j)
            {
                dis = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
                if(dis >= 10 && dis <= 1000)
                {
                    a[tot].there = i;
                    a[tot].here = j;
                    a[tot].w = dis;
                    tot++;
                }
            }
        sort(a, a + tot, cmp);
        int flag = 0;
        for(int i = 0; i < tot; ++i)
            if(judge(a[i].there, a[i].here))
            {
                ans += a[i].w;
                flag++;
            }
        if(flag == n - 1)
            printf("%.1f\n", ans * 100);
        else
//            cout << "oh!" << '\n';
            printf("oh!\n");
    }
    return 0;
}

Code of Prim

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int inf = 0x3f3f3f3f;

int n;
bool vis[125];
int x[125], y[125];
double mp[125][125], low[125], ans;///low[i]表示已成图所有点到点i的最小权值

void prim()
{
    ans = 0;
    double mmin;
    memset(vis, 0, sizeof(vis));

    int pos = 1;///从点1开始
    vis[1] = 1;
    for(int i = 1; i <= n; ++i)
        low[i] = mp[pos][i];

    int cnt = n;
    while(--cnt)///只需连接 n - 1条，此循环便是 n - 1 次
    {
        mmin = inf;///此次连接中的最小权值
        for(int j = 1; j <= n; ++j)
        {
            if(vis[j] == 0 && low[j] < mmin)
            {
                mmin = low[j];
                pos = j;
            }
        }

        if(mmin == inf)///某次循环所查询点皆为不可连接点
        {
            cout << "oh!" << '\n';
            return ;
        }

        ///处理下一个点(pos)之前更新 low[]
        vis[pos] = 1;
        ans += mmin;
        for(int j = 1; j <= n; ++j)
            if(vis[j] == 0 && low[j] > mp[pos][j])
                low[j] = mp[pos][j];
    }
    printf("%.1f\n", ans * 100);
}

int main()
{
    int t;
//    freopen("00in.tex", "r", stdin);
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i)
            scanf("%d%d", &x[i], &y[i]);
        memset(mp, 0, sizeof(mp));
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j)
            {
                mp[i][j] = sqrt(1.0 * ((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])));
//                cout << i << ' ' << j << ' ' << mp[i][j] << '\n';
                if(mp[i][j] < 10 || mp[i][j] > 1000)
                    mp[i][j] = inf;
            }
        prim();
    }
    return 0;
}