UVA11631 Dark roads 题解

· · 题解

前情提要

题目链接

更好的阅读体验

题目大意

若一个图删去一定的边仍能保持连通，求这些边权值加和的最大值。

实际分析

一眼最小生成树板子。

删掉一些边后边权值加和的最大值，不就等于整张图减去边权值加和的最小值吗？

那么就是最小生成树板子题了，我这里使用的是 Kruskal 算法。

这里就要涉及到最小生成树的相关的知识点了，建议大家去看看这两道题。

当然我这里还是简述一下最小生成树的概念以及重要属性。

概念：一个连通图的生成树是一个极小的连通子图，它包含图中全部的 n 个顶点，但只有构成一棵树的 n-1 条边。

属性（这里只介绍最重要的一个属性）：生成树当中不存在环。

当你充分理解了以上的知识点后，你做这道题就很轻松了。

当然如果你还是不懂，我这里还贴心的准备里一个视频。

代码部分

#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
const int MAXX = 2000005;
int cnt, sum, sum_sum, n, m;
int fa[MAXX];
struct edge {
    int u, v, w;
} e[MAXX];
int find(int x) {
    if (x != fa[x]) return fa[x] = find(fa[x]);
    return x;
}
bool cmp(edge a, edge b) {
    return a.w < b.w;//排序最小的边
}
void tree() {//Kruskal 大法好
    sort(e + 1, e + 1 + m, cmp);
    for (int i = 1; i <= m; i++) {
        int u = find(e[i].u);
        int v = find(e[i].v);
        if (u == v) {
            continue;//如果有环则跳过
        }
        sum += e[i].w;//累加最小生成树的权值和
        fa[u] = v;//设置u的爸爸是v，当然这里写 fa[v]=u 也没问题
    }
}
signed main() {
    while (cin >> n >> m) {
        if (n == 0 and m == 0) {
            break;
        }
        sum_sum = 0;
        sum = 0;
        memset(e, 0, sizeof(e));//记得清空
        for (int i = 0; i <= n - 1; i ++) {
            fa[i] = i;//将自己设定为自己的爸爸
        }
        for (int i = 1; i <= m; i ++) {
            cin >> e[i].u >> e[i].v >> e[i].w;
            sum_sum += e[i].w;//累加整张图的边权之和
        }
        tree();
        cout << sum_sum - sum << endl;//边权之和减去最小边权和就是一删去一定的边仍能保持连通的边权值和的最大值
    }
    return 0;
}

完结撒花！