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

news/2024/9/23 11:19:14/

2024年4月12日饿了么春招实习试题【第三题】-题目+题解+在线评测,2024.4.12,饿了么机试

  • 🏩题目一描述:
    • 样例1
    • 样例2
    • 解题思路一:[Kruskal 算法](https://baike.baidu.com/item/%E5%85%8B%E9%B2%81%E6%96%AF%E5%8D%A1%E5%B0%94%E7%AE%97%E6%B3%95/4455899?fr=ge_ala) 最小生成树(MST,Minimum Spanning Tree)
    • 解题思路二:
    • 解题思路三:java, c++

🏩题目一描述:

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

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

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

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

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

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

数据范围

  • 2 ≤ n ≤ 1 0 5 2 \leq n \leq 10^5 2n105
  • 0 ≤ m ≤ 1 0 5 0 \leq m \leq 10^5 0m105
  • 1 ≤ u , v ≤ n 1 \leq u, v \leq n 1u,vn
  • 1 ≤ w ≤ 1 0 9 1 \leq w \leq 10^9 1w109

样例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 += wroads.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 -= wcnt -= 1maxv = 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 = 0for _ in range(m):u, v, w = map(int, input().split())roads.append((u, v, w))total += wroads.sort(key=lambda x: x[2])p = list(range(n + 1))cnt = nmaxv = 0for u, v, w in roads:u = find(p, u)v = find(p, v)if u != v:p[u] = vtotal -= wcnt -= 1maxv = 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)


创作不易,观众老爷们请留步… 动起可爱的小手,点个赞再走呗 (๑◕ܫ←๑)
欢迎大家关注笔者,你的关注是我持续更博的最大动力


原创文章,转载告知,盗版必究



在这里插入图片描述


在这里插入图片描述
♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠


http://www.ppmy.cn/news/1462082.html

相关文章

AIGC时代已至,你准备好抓住机遇了吗?

一、行业前景 AIGC&#xff0c;即人工智能生成内容&#xff0c;是近年来人工智能领域中发展迅猛的一个分支。随着大数据、云计算、机器学习等技术的不断进步&#xff0c;AIGC已经取得了显著的成果&#xff0c;并且在广告、游戏、自媒体、教育、电商等多个领域实现了广泛应用。…

代码复现|Demucs Music Source Separation

一、背景介绍 Demucs是一个开源的音源分离项目。 Demucs在算法层面前后经历了三次大版本的进化&#xff0c;最原始的V1版本是&#xff1a;编解码LSTM。具体算法原理图如下所示。该版本在时域进行音源分离。关于阅读笔记请点击这篇文章。 V1版本原理图 V2版本是同时使用时域和频…

基于C++和OpenCv对视频进行抽帧

下列代码演示了从某.MP4视频文件内以一秒一帧进行抽取&#xff0c;并对抽出的图片以秒数命名的全过程。 #include <opencv2/opencv.hpp> #include <iostream> #include <string> #include <direct.h>using namespace cv; using namespace std;void ex…

Vue组件---进阶

能够掌握vue组件进阶知识使用能够掌握自定义指令能够完成tabbar案例 一.Vue 组件进阶 1.动态组件 目标&#xff1a;多个组件使用同一个挂载点&#xff0c;并动态切换 1. 准备被切换的 - UserName.vue / UserInfo.vue 2个组件 UserName.vue<template> <div><d…

【CTF Web】NSSCTF 3863 [LitCTF 2023]导弹迷踪 Writeup(JS分析+源码泄漏+信息收集)

[LitCTF 2023]导弹迷踪 你是一颗导弹&#xff0c;你需要&#xff0c;飞到最后&#xff01;&#xff08;通过6道关卡就能拿到flag哦~ Flag形式 NSSCTF{} 出题人 探姬 解法 查看网页源代码。 flag 应该在这些文件里面。 <!-- Game files --><script type"applicat…

机器学习之sklearn基础教程(第三篇:模型选择和评估)

机器学习之sklearn基础教程&#xff08;第三篇&#xff1a;模型选择和评估&#xff09; 1. 模型选择 在机器学习任务中&#xff0c;选择合适的模型是非常重要的。不同的模型适用于不同的问题类型和数据特征。 在模型选择过程中&#xff0c;有几个常用的方法和原则&#xff1a;…

面向对象 08:接口的相关知识,接口的基本特性、作用、使用方法等,以及普通类 / 抽象类 / 接口三者的区分

一、前言 记录时间 [2024-05-16] 系列文章简摘&#xff1a; 面向对象 04&#xff1a;三大特性之——封装&#xff0c;封装的含义和作用&#xff0c;以及在 Java 中的使用方式&#xff0c;附完整的测试案例代码 面向对象 05&#xff1a;三大特性之——继承&#xff0c;继承在 Ja…

Vue.directive注册(全局与局部)自定义指令使用详解与实战

指令定义函数提供了几个钩子函数&#xff08;可选&#xff09;&#xff1a; bind: 只调用一次&#xff0c;指令第一次绑定到元素时调用&#xff0c;可以定义一个在绑定时执行一次的初始化动作。inserted: 被绑定元素插入父节点时调用&#xff08;父节点存在即可调用&#xff0…