CF1108F MST Unification

题目地址：CF1108F MST Unification

最小生成树kruskal算法的应用

只需要在算法上改一点点

当扫描到权值为 \(val\) 的边时，我们将所有权值为 \(val\) 的边分为两类：

一类是边连起来的两点已经联通，这一类边一定不加入MST，不需要对其进行操作

另一类是边连起来的两点还未联通，这一类边可能需要加入最小生成树MST（注意是可能），我们对其进行操作

如果在操作的过程中发现某一条边不加入MST，则这一条边我们需要对其+1以确保MST的唯一性

时间复杂度为 \(O(m\ log\ m)\)

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 200006;
int n, m, fa[N], ans;
struct E {
    int x, y, z;
    bool operator < (const E w) const {
        return z < w.z;
    }
} a[N];

int get(int x) {
    if (x == fa[x]) return x;
    return fa[x] = get(fa[x]);
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].z);
    sort(a + 1, a + m + 1);
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 1, j = 1; i <= m; i = j) {
        while (j <= m && a[j].z == a[i].z) ++j;
        int cnt = j - i;
        for (int t = i; t < j; t++) {
            int x = get(a[t].x), y = get(a[t].y);
            if (x == y) --cnt;
        }
        for (int t = i; t < j; t++) {
            int x = get(a[t].x), y = get(a[t].y);
            if (x == y) continue;
            --cnt;
            fa[x] = y;
        }
        ans += cnt;
    }
    cout << ans << endl;
    return 0;
}

巴特西

CF1108F MST Unification

题目地址：CF1108F MST Unification

最小生成树kruskal算法的应用

只需要在算法上改一点点

当扫描到权值为 \(val\) 的边时，我们将所有权值为 \(val\) 的边分为两类：

一类是边连起来的两点已经联通，这一类边一定不加入MST，不需要对其进行操作

另一类是边连起来的两点还未联通，这一类边可能需要加入最小生成树MST（注意是可能），我们对其进行操作

如果在操作的过程中发现某一条边不加入MST，则这一条边我们需要对其+1以确保MST的唯一性

时间复杂度为 \(O(m\ log\ m)\)

代码：

最新文章

热门文章