最小生成树

最小生成树：能够连接所有点的最小边权之和，但是任意两点之间的距离不一定最短（与最短路区别）
Prim算法：算法思路大致和dijkstra算法一致，只是dist不是距离源点的距离了，而是距离集合的距离（单独的一条边权）
kruskal算法：先对边进行排序，利用并查集判断是否所有边都加进来了，由于已经排好序了，加进来的边权和在所有边都加进来后一定就是最小的

#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 100010, INF = 0x3f3f3f;
int m, n, res, cnt;
int g[N][N];
int dist[N];
bool st[N];

int P[N];
struct Edge
{
   int a, b, w;
   bool operator<(const Edge &W) const
   {
      return w < W.w;
   }
} edges[M];

int prim()
{
   memset(dist, 0x3f, sizeof dist);
   for (int i = 0; i < n; i++)
   {
      int t = -1;
      for (int j = 1; j <= n; j++)
      {
         if (!st[j] && (t == -1 || dist[t] > dist[j]))
            t = j;
      }
      st[t] = true;
      if (i && dist[t] == INF)
         return INF; // 说明没标记的点最小都是INF了，说明图不连通
      if (i)
         res += dist[t];
      for (int j = 1; j <= n; j++)
      {
         if (dist[j] > g[t][j])
            dist[j] = g[t][j];
      }
   }
   return res;
}

int find(int x)
{
   if (p[x] != x)
      p[x] = find(p[x]);
   return p[x];
}
int kruskal()
{
   sort(edges, edges + m);

   for (int i = 1; i <= n; i++)
      p[i] = i; // 初始化并查集

   int res = 0, cnt = 0;
   for (int i = 0; i < m; i++)
   {
      int a = edges[i].a, b = edges[i].b, w = edges[i].w;

      a = find(a), b = find(b);
      if (a != b) // 如果两个连通块不连通，则将这两个连通块合并
      {
         p[a] = b;
         res += w;
         cnt++;
      }
   }

   if (cnt < n - 1)
      return INF;
   return res;
}
int main()
{
   cin >> m >> n;

   // while (m--)
   // {
   //    int a, b, c;
   //    cin >> a >> b >> c;
   //    g[a][b] = g[b][a] = min(g[a][b], c);
   // }
   // int t = prim();
   // if (t == INF)
   //    cout << "impossible" << endl;
   // else
   //    cout << t << endl;
   // return 0;

   int res = 0, cnt = 0;
   for (int i = 0; i < m; i++)
   {
      int a, b, c;
      cin >> a >> b >> c;
      // edges[i].a = a, edges[i].b = b, edge[i].w = c;
      edges[i] = {a, b, c};
   }
   int t = kruskal();
   if (t == INF)
      cout << "impossible" << endl;
   else
      cout << t << endl;
   return 0;
}