UVa 10397 - Connect the Campus

传送门

UVa 10397 - Connect the Campus

题意

学校要联网,已经有一些楼之间有电缆了,求权值的最小和.

思路

MST。只要把已经给出的楼的权值变为0即可。

在Find函数里忘了把查找过的结点变为根的儿子,完全一样的思路,愣是和别人差了200ms,提交了二十来次才发现( TДT),不过这也让我熟悉了Kruskal。。。

Prim算法做这题可以达到50ms,马上去看看(๑•̀ㅂ•́)و✧

代码

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int EMAXN = 3e5;
const int DMAXN = 800;
 
struct POINT
{
    int x, y;
}pit[DMAXN];
 
double dis[EMAXN], ans;
int u[EMAXN], v[EMAXN], r[EMAXN], p[DMAXN], mp[DMAXN][DMAXN];
int ncable, n, nbuild;
 
int cmp(const int i, const int j)
{
    return dis[i] < dis[j];
}
 
int Find(int x)
{
    return p[x] == x ? x : (p[x] = Find(p[x]));
}
 
void Kruscal()
{
    int i, j;
    sort(r, r + n, cmp);
    for (int i = 0; i < n; i++)
    {
        int e = r[i];
        int x = Find(u[e]), y = Find(v[e]);
        if (x != y)
            ans += dis[e], p[x] = y;
    }
}
 
int main()
{
    //freopen("input.txt", "r", stdin);
    int i, j, a, b;
    while (~scanf("%d", &nbuild))
    {
        memset(mp, 0, sizeof mp);
        n = 0, ans = 0;
        for (i = 1; i <= nbuild; i++)
        {
            p[i] = i;
            scanf("%d%d", &pit[i].x, &pit[i].y);
        }
        scanf("%d", &ncable);
        for (i = 0; i < ncable; i++)
        {
            scanf("%d%d", &a, &b);
            mp[a][b] = mp[b][a] = 1;
        }
        for (i = 1; i <= nbuild; i++)
            for (j = i + 1; j <= nbuild; j++)
            {
                u[n] = i, v[n] = j, r[n] = n;
                if (mp[i][j])
                    dis[n++] = 0;
                else
                    dis[n++] = hypot(pit[i].x - pit[j].x, pit[i].y - pit[j].y);
            }
        Kruscal();
        printf("%.2f\n", ans);
    }
    return 0;
}

Powered by Jekyll and Theme by solid