53. 寻宝

#include<iostream>
#include<vector>
using namespace std;
int main() {
    int v, e;
    int x, y, k;
    cin >> v >> e;  
    // 填一个默认最大值，题目描述val最大为10000
    vector<vector<int>> grid(v, vector<int>(v, 10001));
    while (e--) {
        cin >> x >> y >> k;
        // 因为是双向图，所以两个方向都要填上
        grid[x - 1][y - 1] = k;
        grid[y - 1][x - 1] = k; 
        
    }
    // 所有节点到最小生成树的最小距离
    vector<int> minDist(v, 10001);
    
    // 这个节点是否在树里
    vector<bool> isInTree(v, false);
    
    //vector<int> parent(n, 10001);
    
    //这里的设计 极其巧妙，和下面for循环是联动的，不用计算节点1
    minDist[0] = 0; // 从节点1开始加入到树中 
    
    // 我们只需要循环 n-1次，建立 n - 1条边，就可以把n个节点的图连在一起
    for (int i = 1; i < v; i++) {
        int cur = -1;
        for (int j = 0; j < v; j++) {
            // 这个if里信息量很大
            if (!isInTree[j] && (cur == -1 || minDist[j] < minDist[cur])) {
                cur = j;
            }
        }
        isInTree[cur] = true;
        for (int j = 0; j < v; j++) {
            if (!isInTree[j] && grid[cur][j] < minDist[j]) {
                minDist[j] = grid[cur][j];
                // 这个指的顺序要要求去一下
                //parent[cur] = i;
            }
        }
        
    }
    int result = 0;
    for (int i = 1; i < v; i++) {
        result += minDist[i];
    }
    cout << result << endl;

}

// Prim最小生成树算法
#include<bits/stdc++.h>
using namespace std;

int n, m;

void solve() {
    // 存储边,代表两个边之间的距离,初始化为一个很大的值,这代表一开始没有路径
    vector<vector<int>> grid(n, vector<int>(n, 0x3f3f3f3f)); 
    for(int i = 0; i < m; ++i) { 
        int x, y, k;
        cin >> x >> y >> k;
        // 因为是无向图,所以这里两个方向都要填上k
        grid[x - 1][y - 1] = k;
        grid[y - 1][x - 1] = k;
    }
    // 用来记录前驱节点到该节点的最小距离
    vector<int> minDist(n, 10001);
    // 用来记录节点是否在最小生成树中
    vector<bool> isInTree(n, false);
    // 通用的模板中需要一个parent数组,用来记录前驱结点
    // 但本题不需要知道路径
    // 所以不用parent数组也可以得到答案
    // vector<int> parent(n, 0x3f3f3f3f);
    minDist[0] = 0;
    // 需要找到n - 1条边
    for(int k = 0; k < n - 1; ++k) {
        // vec用来表示当前找到的距离最近的节点
        int vec = -1;
        // 找到当前的最近节点,注意是未在最小生成树中的节点
        for(int i = 0; i < n; ++i) {
            if(!isInTree[i] && (vec == -1 || minDist[i] < minDist[vec])) {
                vec = i;
            }
        }
        // 标记该节点已经加入最小生成树
        isInTree[vec] = true;
        // 更新目前找到的这个节点到其他节点的最小值
        // 注意这里也需要其他节点是未被加入最小生成树的
        for(int i = 0; i < n; ++i) {
            if(!isInTree[i] && grid[vec][i] < minDist[i]) {
                minDist[i] = grid[vec][i];
                // 同理, 下面这个parent也可以隐去
                // parent[i] = vec; 
            }
        }
    }
    int ans = 0;
    // 得到路径和
    for(int i = 0; i < n; ++i) {
        ans += minDist[i];
    }
    cout << ans << endl;
}


int main() {
    while(cin >> n >> m) {
        solve();
    }
    return 0;
}

/* 
 * 可以用 kruskal 算法来求最小生成树
 * 将所有的边按照权值大小做升序排序，从权值最小的边开始选择，只要此边不和已选择的边一起构成环路，就可以选择它组成最小生成树
 * 可以通过并查集来判断两个节点是否连通便可以判断当前选择的边是否会和已选择的边构成环路
 */
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 并查集模板
class UF {
private:
    int count;              // 连通分量的个数
    vector<int> parent;     // 存储每个节点的根节点
public:
    UF(int n) : count(n) {
        parent.resize(n);
        for (int i = 0; i < n; ++i) parent[i] = i;
    }

    // 将节点 p 和节点 q 连通
    void unionNew(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ) return;
        parent[rootQ] = rootP;
        --count;
    }

    // 判断节点 p 和节点 q 是否连通
    bool connected(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        return rootP == rootQ;
    }

    // 查找节点 x 的根节点
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    // 返回连通分量个数
    int getCount() {
        return count;
    }
};

int main() {
    int v, e;
    cin >> v >> e;
    vector<vector<int>> edges(e, vector<int>(3));
    for (auto& edge : edges) {
        cin >> edge[0] >> edge[1] >> edge[2];
    }

    // 对边按权值大小做升序排序
    sort(edges.begin(), edges.end(), [&] (const auto& a, const auto& b) {
        return a[2] < b[2];
    });

    // kruskal 算法
    UF uf(v);
    int res = 0;
    // 按权值从小到大遍历每条边，并判断当前的边是否会和已选择的边构成环路
    for (const auto& edge : edges) {
        int from = edge[0] - 1, to = edge[1] - 1, val = edge[2];
        // 若当前的边的起点和终点已经连通，则跳过
        if (uf.connected(from, to)) continue;
        // 若当前的边的起点和终点未连通，则将当前边的权值加入 res，并将起点和终点连通起来
        res += val;
        uf.unionNew(from, to);
        // 如果当前连通分量的个数为 1，则说明已经构建出了最小生成树，跳出循环
        if (uf.getCount() == 1) break;
    }
    cout << res << endl;
    return 0;
}

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    // 最小生成树的Prim算法
    public static void prim(int numberOfNodes, int numberOfEdges, int[][] graph) {
        int[] distanceToTree = new int[numberOfNodes + 1]; // 存储各个节点到生成树的距离
        boolean[] isInTree = new boolean[numberOfNodes + 1]; // 节点是否被加入到生成树中
        int[] parent = new int[numberOfNodes + 1]; // 节点的前驱节点

        Arrays.fill(distanceToTree, Integer.MAX_VALUE); // 初始化距离数组为一个很大的数
        distanceToTree[1] = 0; // 从 1 号节点开始生成

        for (int i = 0; i < numberOfNodes; i++) { // 每次循环选出一个点加入到生成树
            int closestNode = -1;
            for (int j = 1; j <= numberOfNodes; j++) { // 每个节点一次判断
                if (!isInTree[j] && (closestNode == -1 || distanceToTree[j] < distanceToTree[closestNode])) {
                    closestNode = j;
                }
            }

            isInTree[closestNode] = true; // 选择该点

            for (int k = 1; k <= numberOfNodes; k++) { // 更新生成树外的点到生成树的距离
                if (distanceToTree[k] > graph[closestNode][k] && !isInTree[k]) {
                    distanceToTree[k] = graph[closestNode][k]; // 更新距离
                    parent[k] = closestNode; // 从 closestNode 到 k 的距离更短，k 的前驱变为 closestNode.
                }
            }
        }
        int result = 0;
        for (int i = numberOfNodes; i > 1; i--) { // 计算最小生成树的权值
            result += graph[i][parent[i]];
        }
        System.out.println(result);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int numberOfNodes = scanner.nextInt();
        int numberOfEdges = scanner.nextInt();

        int[][] graph = new int[numberOfNodes + 1][numberOfNodes + 1];
        for (int i = 1; i <= numberOfNodes; i++) {
            Arrays.fill(graph[i], Integer.MAX_VALUE); // 各个点之间的距离初始化成很大的数
        }

        while (numberOfEdges-- > 0) {
            int nodeA = scanner.nextInt();
            int nodeB = scanner.nextInt();
            int weight = scanner.nextInt();
            graph[nodeA][nodeB] = weight; // 存储权重
            graph[nodeB][nodeA] = weight; // 无向图，存储两次。
        }

        prim(numberOfNodes, numberOfEdges, graph); // 求最小生成树
    }
}

from collections import deque

n, e = map(int, input().split())
edges = []
for _ in range(e):
    u, v, w = map(int, input().split())
    edges.append((w, u-1, v-1))
edges.sort()
ans = 0
parent = list(range(n))


def find(u):
    if parent[u] == u:
        return u
    p = find(parent[u])
    parent[u] = p
    return p


cnt = 0

for w, u, v in edges:
    pu = find(u)
    pv = find(v)
    if find(u) != find(v):
        ans += w
        cnt += 1
        if cnt == n-1:
            break
        parent[pv] = pu

print(ans)