无向图最小生成树
基准时间限制：1 秒 空间限制：131072 KB 分值: 0 难度：基础题
N个点M条边的无向连通图，每条边有一个权值，求该图的最小生成树。
Input
第1行：2个数N,M中间用空格分隔，N为点的数量，M为边的数量。（2 <= N <= 1000, 1 <= M <= 50000)
第2 – M + 1行：每行3个数S E W，分别表示M条边的2个顶点及权值。(1 <= S, E <= N，1 <= W <= 10000)
Output
输出最小生成树的所有边的权值之和。
Input示例
9 14
1 2 4
2 3 8
3 4 7
4 5 9
5 6 10
6 7 2
7 8 1
8 9 7
2 8 11
3 9 2
7 9 6
3 6 4
4 6 14
1 8 8
Output示例
37
图论的基础题。
因为数据规模并不大并不需要对输入数据进行特殊处理。
先任取一点标记为已加入树中，然后枚举每一条边，找到所有连接在树中与不在树中的点的边当中权值最小的加入当前权值之和，并且将不在树中的那一点标记为在树中。
每轮循环往树中加入一点，当进行n次循环时所有点均已加入树中，并且所得的生成树权值之和最小。时间复杂度约为O(mn)
|
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 |
#include <cstdio> #include <cstring> #include <cmath> #include <string> #include <iostream> #include <istream> #define forr(a,b,c) for(int a=b;a<=c;a++) #define MAX(a,b) (a>b)?a:b; #define MIN(a,b) (a<b)?a:b; #define memsett(a) memset(a,sizeof(a),0); using namespace std; int n, m, point, minpoint,link; int a[50001][3]; bool boo[50001]; int main() { point = 0; forr(i, 0, 50000) boo[i] = false; scanf("%d %d", &n, &m); forr(i, 1, m) { scanf("%d %d %d", &a[i][1], &a[i][2], &a[i][3]); } boo[1] = true; forr(i, 2, n) { minpoint = 1000000; forr(j, 1, m) { if (boo[a[j][1]] == true && boo[a[j][2]] == false && a[j][3] < minpoint) { link = a[j][2]; minpoint = a[j][3]; } if (boo[a[j][2]] == true && boo[a[j][1]] == false && a[j][3] < minpoint) { link = a[j][1]; minpoint = a[j][3]; } } point += minpoint; boo[link] = true; } printf("%d", point); } |