基础并查集

HDU5441 Travel

好久没有写单独一题的题解了……最近一直在写专题,2-SAT已经写了半个月了,昨天写到一道带权并查集,没怎么分析数据就直接开写了……结果一直TTTT……

传送门

题意:
一个把消费旅游看成成长标志的大学生想要出去玩。有n个城市,m条路,每条路都有耗费时间,浮躁的大学生在一条路上最多等 limit 分钟,否则他就不去。因为等待时间是固定的,他只能顺应环境,尝试改变自己的 limit ,问有q个limit,他最多能走多少不同的路线。 (起点终点有不相同即为不同)

思路:
并查集处理,得集合中的元素 n ,对每个单独的集合取 \(A_n^2\) 也就是 n*(n-1) ,但是 \(n \le 20000,q \le 5000\),如果每次都重置并跑一便并查集不用想也是要 T 的。这里有两个优化地方:

  • 对每个limit排序
  • 对边权排序

对每一个排序后的limit,遍历边权,如果小于当前limit就加入并查集操作,否则退出。
而对下一个limit询问就从上次退出的位置减一继续操作即可。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#define INF 0x3f3f3f

using namespace std;
const int maxn = 2e4 + 10;
int n, m, q;
int root[maxn];
long long num[maxn];
int head[maxn];
long long ans[maxn];

struct limit_node {
    long long limit;
    int pos;
    bool operator<(const limit_node& a) const
    {
        return limit < a.limit;
    }
} nodes[maxn * 10];

struct node {
    int from;
    int to;
    int val;
    bool operator<(const node& a) const
    {
        return val < a.val;
    }

} edges[maxn * 10];

int findRoot(int x)
{
    return root[x] == x ? root[x] : root[x] = findRoot(root[x]);
}

void init()
{
    for (int i = 0; i <= n; i++) {
        num[i] = 1;
        root[i] = i;
    }
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d %d", &n, &m, &q);
        init();
        for (int i = 1; i <= m; i++)
            scanf("%d %d %d", &edges[i].from, &edges[i].to, &edges[i].val);
        for (int i = 1; i <= q; i++) {
            scanf("%lld", &nodes[i].limit);
            nodes[i].pos = i;
        }
        sort(edges + 1, edges + m + 1);
        sort(nodes + 1, nodes + q + 1);
        int cur = 1, ru, rv;
        for (int cnt = 1; cnt <= q; cnt++) {
            for (; cur <= m; cur++) {
                if (edges[cur].val <= nodes[cnt].limit) {
                    ru = findRoot(edges[cur].from);
                    rv = findRoot(edges[cur].to);
                    if (ru != rv) {
                        root[rv] = ru;
                        num[ru] += num[rv];
                    }
                } else {
                    cur--;
                    break;
                }
            }
            long long res = 0;
            for (int i = 1; i <= n; i++)
                if (root[i] == i)
                    res += (num[i] * (num[i] - 1));
            ans[nodes[cnt].pos] = res;
        }
        for (int i = 1; i <= q; i++)
            printf("%lld\n", ans[i]);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注