建立网站的步骤筝晃湖南岚鸿官网_红河网站建设设计_百度推广客服电话多少_潮州seo

现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。

输入格式

输入数据包括城镇数目正整数 n（≤1000）和候选道路数目 m（≤3n）；随后的 m 行对应 m 条道路，每行给出 3 个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从 1 到 n 编号。

输出格式

输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出 −1，表示需要建设更多公路。

输入样例

6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3

输出样例

12

思路

这道题是一个很典型的最小生成树问题。
这里使用的是prim算法。
所谓prim算法就是这样的

1. 选择一个结点，将这个结点放入生成树中（初始化最小生成树），并将其lowcost置为0。
2. 求这一点到未访问的、可到达的顶点的权值。若出现比之前更小的权值，则要修改，否则，不用。
3. 选一条一个顶点在树上，一个顶点在树外的边上的，并且权值最小的顶点（这包括之前的），并加入树中，并将其lowcost置为0。
4. 重复2、3直到U=V
   
   简而言之，就是初始化—>更新参数—>选择结点—>更新参数—>选择结点—>更新参数—>选择结点—>……—直到U=V—>结束

Code

#include <bits/stdc++.h>
using namespace std;int map_[1020][1020];
int nodesw[1020];
int parent[1020];
bool isused[1020];
int sum = 0;void init(int N) {for(int i = 1; i <= N; ++i) {nodesw[i] = INT_MAX;}
}int find(int b, int N) {int minw = INT_MAX, minA = -1;for(int i = 1; i <= N; ++i) {if(minw > nodesw[i] && isused[i] == false) {minw = nodesw[i];minA = i;}}return minA;
}void add1(int b, int N) {for(int i = 1; i <= N; ++i) {if(map_[b][i] != 0 && map_[b][i] < nodesw[i] && isused[i] == false) {nodesw[i] = map_[b][i];parent[i] = b;}}
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int N, rest, M, A , B, w, minA, minw = INT_MAX;cin >> N >> M;rest = N;init(N);for(int i = 1; i <= M; ++i) {cin >> A >> B >> w;map_[A][B] = map_[B][A] = w;if(minw > w) {minA = A;minw = w;}}nodesw[minA] = 0;isused[minA] = true;parent[minA] = -1;while(rest--) {add1(minA, N);minA = find(minA, N);if(minA == -1) break;sum += nodesw[minA];isused[minA] = true;}for(int i = 1; i <= N; ++i) {if(!isused[i]) {cout << -1;return 0;}}cout << sum;
}