蓝桥杯真题 - 缴纳过路费 - 题解

题目链接：https://www.lanqiao.cn/problems/19736/learning/

个人评价：难度 2 星（满星：5）
前置知识：并查集

整体思路

• 按边权从小到大处理，将处理过的边的两个端点合入一个并查集中；
• 由此，在处理到第 $i$ 条边时，如果边的两个端点不在并查集中，那么这两个端点各自在的并查集中所有端点，都必须经过这条边才能到达对面的端点，所以该边两端所有点之间的“最贵”收费就是这条边的权值，因此如果该边权值在区间 $[L,R]$ 内，那么这条边对答案的贡献就是两边并查集节点数的乘积。

过题代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn = 200000 + 100;
struct Edge {
    int u, v, w;
    Edge() {}
    Edge(int u, int v, int w): u(u), v(v), w(w) {}
};

bool operator<(const Edge &a, const Edge &b) {
    return a.w < b.w;
}

int n, m, l, r, u, v, w;
LL ans;
int fa[maxn], num[maxn];
Edge edge[maxn];

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

int findF(int x) {
    return x == fa[x] ? x : fa[x] = findF(fa[x]);
}

void union_(int x, int y) {
    x = findF(x);
    y = findF(y);
    if (x != y) {
        fa[x] = y;
        num[y] += num[x];
    }
}

int main() {
#ifdef ExRoc
    freopen("test.txt", "r", stdin);
#endif // ExRoc
    ios::sync_with_stdio(false);

    cin >> n >> m >> l >> r;
    init();
    for (int i = 1; i <= m; ++i) {
        cin >> edge[i].u >> edge[i].v >> edge[i].w;
    }
    sort(edge + 1, edge + 1 + m);
    for (int i = 1; i <= m; ++i) {
        u = findF(edge[i].u);
        v = findF(edge[i].v);
        w = edge[i].w;
        if (w >= l && w <= r && u != v) {
            ans += num[u] * num[v];
        }
        union_(u, v);
    }
    cout << ans << endl;

    return 0;
}