7-10 公路村村通 prim算法笔记

现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。
输入格式:
输入数据包括城镇数目正整数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

【7-10 公路村村通 prim算法】输出样例:

12

prim算法中的思想和Dijkstra算法很像。只是在最短距离那儿用了集合S来代替Dijkstra算法中的起点。
代码实现（c++）：

#include #include #include using namespace std; const int maxv = 1010; const int inf = 1000000; int G[maxv][maxv]; intd[maxv],n,m; //d表示顶点与集合S的最短距离 bool vis[maxv] = {false}; int prim() {fill(d,d+maxv,inf); d[1] = 0; //城市是1-N，只有1号顶点到集合S的距离为0，其余全为inf int s = 0; //存放最小生成树的权值之和 for (int i=1; i<=n; i++) { int u=-1,min=inf; for (int j=1; j<=n; j++) { if (vis[j]==false&&d[j]G[u][v]) { d[v]=G[u][v]; //u为中介可以使v离集合S更近 } } } return s; } int main() { int u,v,w; cin>>n>>m; fill(G[0],G[0]+maxv*maxv,inf); for(int i=0; i>u>>v>>w; G[u][v]=w; G[v][u]=w; } int s=prim(); cout<; return 0; }