question linked

题目描述

LL 城一共有 N* 个小区。

小明是城市建设的规划者，他计划在城市修 M* 条路，每修建一条路都要支付工人们相应的工钱（需要支付的工钱 == 路的长度）。

然而小明所拿到的经费并不够支付修建 M条路的工钱，于是迫于无奈，他只能将计划改变为修建若干条路，使得 N 个小区之间两两联通。

小明希望尽量剩下更多的经费投入到别的项目中，因此请你通过程序帮他计算出完成计划所需的最低开销。

输入描述

输入第一行包含三个正整数 N,M。

第 22 到 M+1 行每行包含三个正整数 u,v,wu,v,w，表示 u↔vu↔v 之间存在一条距离为 ww 的路。

1≤N≤10^5^，0≤m≤3×10^5^，1≤ui,vi≤N，0≤wi≤10^9^。

输出描述

输出占一行，包含一个整数，表示完成计划所需的最低开销。

若无法完成计划，则输出 −1−1。

输入输出样例

示例 1

输入

1
2
3
4
5
6
7
5 6
1 2 2
1 3 7
1 4 6
2 3 1
3 4 3
3 5 2

输出

1
8

kruskal algorithm

时间复杂度:O(M * log(M));稀疏图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
const int N = 1e5 + 10, M = 3 * N, INF = 0x3f3f3f3f;
struct Edge {
  int a, b, w;
  bool operator < (const Edge & W ) {
      return w < W.w;
  }//kruskal先找最小边排序;
}edges[N];
int p[N];//并查集找公共祖先，则为连通的，那么不能取;
int find( int x){
  if (p[x] != x) p[x] = find(p[x]);//找到下一个没有用过的点;
  return p[x];
}
int kruskal(){

  sort(edges, edges + m);//对m条边排序;
  for (int i = 1; i <= n; i++) p[i] = i;//初始化每个节点的父节点为自己; 

  int cnt = 0, res = 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 ++;
    }
  }
  //n个点的图的最小生成树为n - 1条边;
  if (cnt < n - 1) return 0x3f3f3f3f;

  return res;
}


int main() {
  cin >> n >> m;
  for (int i = 0; i < 6; i++) {
    int a, b, w;
    scanf("%d%d%d", &a, &b, &w);
    edges[i] = {a, b, w};
  }
  int result = kruskal();
  if (result == INF) puts("-1 -");
  else printf("%d", result);

  return 0;
}

*** prim***

时间复杂度O(N ^ N + M);稠密图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

const int N = 1e4, M = 3e4 + 10, INF = 0x3f3f3f3f;
int n, m;
int g[N][N];
int dist[N];
bool st[N];

int prim() {
    memset(dist, 0x3f, sizeof dist);
    int res = 0;
    for (int i = 0; i < n; i++) {
        int t = -1;
        for (int j = 1; j <= n; j++) {
            if (!st[j] && (t == -1 || dist[j] < dist[t])) {
                t = j;
            }
        }
        if (i && dist[t] == INF) return INF;
        if (i) res += dist[t];
        st[t] = true;
        for (int j = 1; j <= n; j++) {
            dist[j] = min(dist[j], g[t][j]);
   //松弛操作有点类似dijkstra算法，但这是该点到最小生成树的最短距离，而dijkstra是到起点的最短距离
        }
    }
    return res;
}

int main() {
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);  // 初始化邻接矩阵为INF
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        if (c < g[a][b]) {
            g[a][b] = c;
            g[b][a] = c;
        }
    }
    int result = prim();
    cout << result << endl;
    return 0;
}