Problem
Find the minimum spanning tree of the graph.
Input
On the first line there will be two integers N - the number of nodes and M - the number of edges. (1 <= N <= 10000), (1 <= M <= 100000)
M lines follow with three integers i j k on each line representing an edge between node i and j with weight k. The IDs of the nodes are between 1 and n inclusive. The weight of each edge will be <= 1000000.
Output
Single number representing the total weight of the minimum spanning tree on this graph. There will be only one possible MST.
Sample Input
4 5
1 2 10
2 3 15
1 3 5
4 2 2
4 3 40
Sample Output
17
思路
最小生成树模板题，Prim就好，注意输出结果int会溢出，要开到long。
代码
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 10005
#define INF 0x3f3f3f3f
using namespace std;
int cost[N][N];
int mincost[N];
bool used[N];
int V, E;
long Prim() {
memset(mincost, 0x3f, sizeof(mincost));
memset(used, 0, sizeof(used));
mincost[0] = 0;
long res = 0;
while (1) {
int v = -1;
for (int u = 0; u < V; u++) {
if (!used[u] && (v == -1 || mincost[u] < mincost[v]))v = u;
}
if (v == -1)break;
used[v] = true;
res += mincost[v];
for (int u = 0; u < V; u++) {
mincost[u] = min(mincost[u], cost[v][u]);
}
}
return res;
}
int main() {
int v1, v2, w;
cin >> V >> E;
memset(cost, 0x3f, sizeof(cost));
for (int i = 0; i < E; i++) {
cin >> v1 >> v2 >> w;
cost[v1-1][v2-1] = w;
cost[v2-1][v1-1] = w;
}
cout << Prim() << endl;
return 0;
}
