Kruskal算法要对边排序，然后打个并查集维护，但是实际上Prim有他好玩的地方，就把Dijkstra的到点的距离从dis[v]:dis[u]+w改成边dis[v]:w。

那肯定是Prim好写一点。Prim感觉复杂度是O((n+m)logn)，Kruskal是O(n+mlogm)。

#include
    
     using namespace std;typedef long long ll;const int MAXN = 5005;int n, m, s, t;int dis[MAXN];bool vis[MAXN];vector
     
      
        > G[MAXN];const int INF = 0x3f3f3f3f;priority_queue
       
        
          >pq;int Prim(int s) {    for(int i = 1; i <= n; ++i)        dis[i] = INF;    int cnt = 0, sum = 0;    dis[s] = 0;    pq.push({-dis[s], s});    while(!pq.empty()) {        int u = pq.top().second;        pq.pop();        if(vis[u])            continue;        vis[u] = 1;        ++cnt;        sum += (dis[u]);        for(auto e : G[u]) {            int v = e.first, w = e.second;            if(!vis[v] && w < dis[v]) {                dis[v] = w;                pq.push({-dis[v], v});            }        }    }    if(cnt == n)        return sum;    return -1;}int main() {#ifdef Yinku    freopen("Yinku.in", "r", stdin);#endif // Yinku    scanf("%d%d", &n, &m);    for(int i = 1; i <= m; ++i) {        int u, v, w;        scanf("%d%d%d", &u, &v, &w);        G[u].emplace_back(v, w);        G[v].emplace_back(u, w);    }    int res = Prim(1);    if(res == -1)        puts("orz");    else        printf("%d\n", res);    return 0;}