最小生成树

#include <cstdio>
#include <vector>
#include <queue>
#include <functional>
//#include <iostream>
using namespace std;                     //Prim最小生成数算法

vector<bool> visited;
vector<vector<pair<int, int>>> graph;
priority_queue<pair<int,int>, vector<pair<int, int>>, function<bool(pair<int, int>&, pair<int, int>&)>> pq([](pair<int, int>& a, pair<int, int>& b){return a.second > b.second;});
void Add(int n)
{
    if(visited[n])
    return;
    //cout<<visited[0];
    visited[n] = true;
    for(pair<int, int> edge : graph[n])
    {
        int end = edge.first;
        int cost = edge.second;
        if(visited[end])
        continue;
        else
        pq.push(edge);
    }
}
int main() {
    int n, m;
    scanf("%d%d", &n , &m);
    visited.resize(n, false);
    graph.resize(n, vector<pair<int, int>>());
    for(int i = 0; i < m; ++i)
    {
        int start, end, cost;
        scanf("%d%d%d", &start, &end, &cost);
        graph[start - 1].push_back({end - 1, cost});
        graph[end - 1].push_back({start - 1, cost});
    }
    int mst = 0;
    Add(0);
    while(!pq.empty())
    {
        auto [end, cost] = pq.top();
        pq.pop();
       // cout<< end;
        if(visited[end])
        continue;
        else
        {
            mst += cost;
            Add(end);
        } 
    }
    printf("%d\n", mst);
    return 0;
}

#克鲁斯卡尔算法
import sys
n,m =map(int, sys.stdin.readline().strip().split())
edges=[]
for i in range(m):
    a,b,c = map(int, sys.stdin.readline().strip().split())
    edges.append((a-1,b-1,c))
edges = sorted(edges,key=lambda x:x[2])
par = list(range(n))
sz = [1]*n
def findGroupId(node):
    global par
    if par[node] == node:
        return node
    else:
        return findGroupId(par[node])
def union(g_x,g_y):
    global par
    global sz
    if sz[g_x]>sz[g_y]:
        g_x,g_y = g_y,g_x
    sz[g_y]=sz[g_y]+sz[g_x]
    par[g_x]=g_y
    sz[g_x]=0
    
w = 0
count = 0
for (a,b,c) in edges:
    g_a = findGroupId(a)
    g_b = findGroupId(b)
     
    if g_a ==  g_b: #在同一个组中
        continue
    else:
       w+=c
       union(g_a,g_b)
       count+=1
       if count == n-1:
            break
       #print("par",par)
        
print(w)

# kruskal
import sys
import queue as Q
lines = sys.stdin.readlines()

n, m = map(int, lines[0].strip().split())

father = [-1 for i in range(n)]
rank = [0 for i in range(n)]
res = 0
get = 0

que = Q.PriorityQueue()

for line in lines[1:m+1]:
    a, b, c = map(int, line.strip().split())
    que.put((c, a-1, b-1))

while (get < n-1):
    length, start, target = que.get()
    while(father[start] != -1):
        start = father[start]
    while(father[target] != -1):
        target = father[target]
    if start == target: continue
    if (rank[start] < rank[target]):
        father[start] = target
    else:
        father[target] = start
        if rank[start] == rank[target]:
            rank[start] += 1
    res += length
    get += 1
print (res)

# prim
import sys
import queue as Q
lines = sys.stdin.readlines()

n, m = map(int, lines[0].strip().split())

paths = [list() for i in range(n)]
nodes = [0 for i in range(n)]
res = 0
get = 0

for line in lines[1:m+1]:
    a, b, c = map(int, line.strip().split())
    paths[a-1].append([b-1, c])
    paths[b-1].append([a-1, c])

que = Q.PriorityQueue()
nodes[0] = 1
get = 1
for path in paths[0]:
    que.put((path[1], path[0]))

while(get < n):
    length, target = que.get()
    if nodes[target] == 1: continue
    res += length
    nodes[target] = 1
    for path in paths[target]:
        if nodes[path[0]] == 0:
            que.put((path[1], path[0]))
    get += 1

print (res)