SSL 2687_跳跃_最小生成树

lzusa 发布于 2017-08-14 1 次阅读

题目描述

在平面直角坐标系内有n个点。现在有m个人，每个人都有一个行走距离d，也就是说这个人只能走到与它当前位置距离不大于d的点。问有多少个人可以从任意一个点开始，并能够到达所有点。

 

思路

因为题目要求我们每一个点都要走到，所以我们可以用最小生成树来解决

选出最小生成树中的最长边来进行判断即可

这里用的是克鲁斯卡尔+并查集来写的最小生成树，用prime的优化貌似会快很多

#include 
#include 
#include 
using namespace std;
#define maxn 1001
#define maxm 1000001
struct edge
{
    int from, to;
    double w;
}e[maxm];
struct arr
{
    int x, y;
}b[maxn];
int f[maxn], a[maxn];
int cmp(edge a, edge b)
{
    return a.w < b.w;
}
int find(int x)
{
    if (!f[x]) return x;
    f[x] = find(f[x]);
    return f[x];
}
int insert(int x, int y)
{
    if (find(x) != find(y))
    {
        f[find(x)] = find(y);
        return 1;
    }
    return 0;
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    int m;
    scanf("%d", &m);
    for (int i = 1; i <= m; i++)
        scanf("%d%d", &b[i].x, &b[i].y);
    int l = 0;
    for (int i = 1; i <= m; i++)
        for (int j = i + 1; j <= m; j++)
        {
            e[++l].from = i;
            e[l].to = j;
            e[l].w = sqrt((b[i].x - b[j].x) * (b[i].x - b[j].x) + (b[i].y - b[j].y) * (b[i].y - b[j].y));
        }
    sort(e + 1, e + l + 1, cmp);
    double max = 0.0;
    int tot = 0;
    for (int i = 1; i <= l; i++)
    {
        if (find(e[i].from) != find(e[i].to))
        {
            tot++;
            max = e[i].w;
            insert(e[i].from, e[i].to);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        if (a[i] * 1.0 >= max) ans++;
    printf("%d\n", ans);
}

 

]]>