2024年4月12日饿了么春招实习试题【第三题】-题目+题解+在线评测，2024.4.12，饿了么机试【Kruskal 算法， 最小生成树】

🏩题目一描述：

K小姐计划去 n 个城市旅行。这些城市之间有 m 条双向道路相连,每条道路都有一个美景值 w 。

K小姐希望选择一些道路,使得最终所有城市恰好被分成两个连通块。她可以获得所有被选择的道路的美景值之和。

现在K小姐想知道,她能获得的最大的美景值是多少?如果初始时这些城市已经形成了两个或更多的连通块,则输出 − 1 。

输入格式
第一行包含两个正整数 n 和 m ,分别表示城市的数量和道路的数量。

接下来 m 行,每行包含三个正整数 u, v, w,表示城市 u 和城市 v 之间有一条美景值为 w 的道路。

输出格式
输出一个整数,表示K小姐能获得的最大美景值。如果初始时这些城市已经形成了两个或更多的连通块,则输出 − 1。

数据范围

• $2\le n\le 10^5$
• $0\le m\le 10^5$
• $1\le u,v\le n$
• $1\le w\le 10^9$

样例1

输入

3 3
1 2 4
2 3 3
1 3 2

输出

7

说明

删除前两条边即可，这样有两个连通块:节点1和节在3的连通块，节点2自己为一个连通块。

样例2

输入

4 2
1 2 4
3 4 3

输出

0

说明

初始即为两个连通块，无法删除任何边

OJ链接：
https://codefun2000.com/p/P1818

解题思路一：Kruskal 算法 最小生成树（MST，Minimum Spanning Tree）

cnt = 原图节点的数量n - Kruskal 算法构建的边的数量 = 最终剩下的连通分量的个数
maxv 记录构建连通分量时，边权重的最大值
total 是所有边的权重和

最终cnt（连通分量）有三种情况

1. cnt == 1。说明只有一个连通分量，返回total（构建完最小生成树的剩下的权重）和maxv（最小生成树中的最大权重边）的和！
2. cnt == 2。说明有两个连通分量，直接返回total（构建完两个最小生成树的剩下的权重）
3. cnt > 2。说明连通分量大于3，直接返回-1

n, m = map(int, input().split())
total = 0
roads = []
def find(p, x): # 定义一个查找并查集中元素根节点的函数。它实现了路径压缩，使查询更高效。
    if p[x] != x:
        p[x] = find(p, p[x])
    return p[x]
for _ in range(m):
    u, v, w = map(int, input().split())
    total += w
    roads.append((u, v, w))
roads.sort(key = lambda x: x[2]) # 按边的权重对边进行排序，这是Kruskal算法构建MST的关键步骤。
p = list(range(n+1)) # 并查集 初始化并查集，每个节点的父节点初始化为其自身。
cnt = n
maxv = 0
for u, v, w in roads:
    u = find(p, u)
    v = find(p, v)
    if u != v: # 遍历按权重排序的边，使用并查集判断是否形成环，不形成环则加入MST并更新相关变量。
        p[u] = v # 加入并查集
        total -= w
        cnt -= 1
        maxv = max(maxv, w)

if cnt == 1:
    print(maxv + total)
elif cnt == 2:
    print(total)
else:
    print(-1)

时间复杂度：O(mlogm)
空间复杂度：O(n)

解题思路二：

import sys
input = lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(10**6)

def find(p, x):
    if p[x] != x:
        p[x] = find(p, p[x])
    return p[x]

def main():
    n, m = map(int, input().split())
    roads = []
    total = 0
    for _ in range(m):
        u, v, w = map(int, input().split())
        roads.append((u, v, w))
        total += w
    
    roads.sort(key=lambda x: x[2])
    
    p = list(range(n + 1))
    cnt = n
    maxv = 0
    for u, v, w in roads:
        u = find(p, u)
        v = find(p, v)
        if u != v:
            p[u] = v
            total -= w
            cnt -= 1
            maxv = max(maxv, w)
    
    if cnt == 1:
        print(total + maxv)
    elif cnt == 2:
        print(total)
    else:
        print(-1)

if __name__ == "__main__":
    main()

时间复杂度：O(mlogm)
空间复杂度：O(n)

解题思路三：java, c++

import java.io.*;
import java.util.*;

public class Main {
    static int[] p;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);
        
        int[][] roads = new int[m][3];
        long total = 0;
        for (int i = 0; i < m; i++) {
            input = br.readLine().split(" ");
            roads[i][0] = Integer.parseInt(input[0]);
            roads[i][1] = Integer.parseInt(input[1]);
            roads[i][2] = Integer.parseInt(input[2]);
            total += roads[i][2];
        }
        
        Arrays.sort(roads, (a, b) -> a[2] - b[2]);
        
        p = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            p[i] = i;
        }
        
        int cnt = n;
        int maxv = 0;
        for (int[] road : roads) {
            int u = find(road[0]);
            int v = find(road[1]);
            if (u != v) {
                p[u] = v;
                total -= road[2];
                cnt--;
                maxv = Math.max(maxv, road[2]);
            }
        }
        
        if (cnt == 1) {
            System.out.println(total + maxv);
        } else if (cnt == 2) {
            System.out.println(total);
        } else {
            System.out.println(-1);
        }
    }
    
    static int find(int x) {
        if (p[x] != x) {
            p[x] = find(p[x]);
        }
        return p[x];
    }
}

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> p;

int find(int x) {
    if (p[x] != x) {
        p[x] = find(p[x]);
    }
    return p[x];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    
    vector<vector<int>> roads(m, vector<int>(3));
    long long total = 0;
    for (int i = 0; i < m; i++) {
        cin >> roads[i][0] >> roads[i][1] >> roads[i][2];
        total += roads[i][2];
    }
    
    sort(roads.begin(), roads.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[2] < b[2];
    });
    
    p.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        p[i] = i;
    }
    
    int cnt = n;
    int maxv = 0;
    for (auto& road : roads) {
        int u = find(road[0]);
        int v = find(road[1]);
        if (u != v) {
            p[u] = v;
            total -= road[2];
            cnt--;
            maxv = max(maxv, road[2]);
        }
    }
    
    if (cnt == 1) {
        cout << total + maxv << '\n';
    } else if (cnt == 2) {
        cout << total << '\n';
    } else {
        cout << -1 << '\n';
    }
    
    return 0;
}

时间复杂度：O(mlogm)
空间复杂度：O(n)

♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠