7-121 畅通工程之局部最小花费问题 (35分)
某地区经过对城镇交通状况的调查，得到现有城镇间快速道路的统计数据，并提出“畅通工程”的目标：使整个地区任何两个城镇间都可以实现快速交通（但不一定有直接的快速道路相连，只要互相间接通过快速路可达即可）。现得到城镇道路统计表，表中列出了任意两城镇间修建快速路的费用，以及该道路是否已经修通的状态。现请你编写程序，计算出全地区畅通需要的最低成本。
输入格式:
输入的第一行给出村庄数目N (1≤N≤100)；随后的N(N−1)/2行对应村庄间道路的成本及修建状态：每行给出4个正整数，分别是两个村庄的编号（从1编号到N），此两村庄间道路的成本，以及修建状态 — 1表示已建，0表示未建。
输出格式:
输出全省畅通需要的最低成本。
输入样例:
4
1 2 1 1
1 3 4 0
1 4 1 1
2 3 3 0
2 4 2 1
3 4 5 0
输出样例:
3
思路
题目大意就是构建最小生成树。这里使用的普里姆算法。
如果对读者对普里姆算法不懂的话，推荐看博客：https://blog.csdn.net/yeruby/article/details/38615045，博主写的很详细，很清晰。
下面的是我个人的一些理解：
算法思想：设图G顶点集合为U，首先任意选择图G中的一点作为起始点a，将该点加入集合V，再从集合U-V中找到另一点b使得点b到V中任意一点的权值最小，此时将b点也加入集合V；以此类推，现在的集合V={a，b}，再从集合U-V中找到另一点c使得点c到V中任意一点的权值最小，此时将c点加入集合V，直至所有顶点全部被加入V，此时就构建出了一颗MST。因为有N个顶点，所以该MST就有N-1条边，每一次向集合V中加入一个点，就意味着找到一条MST的边。
个人理解：
也就是找一点A作为开始点，然后找到另一个距离开始点最近的点B连接起来，接着再找一个点C（点C是离点A或者点B最近的那一点），接下来的D点也就是到A,B,C点中最近的那一点，依此类推连接所有点，构成最小生成树。
具体代码解释见AC代码：
#include<bits/stdc++.h>
using namespace std;
int dist[101],cost[101][101],vis[101];
int n,m,i,j,sum=0;
int main(){
cin>>n;
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
cost[i][j]=cost[j][i]=1e9;
}
}
m=n*(n-1)/2;
int x,y,dis,z;
while(m--){
cin>>x>>y>>dis>>z;
if(z==0) cost[x][y]=cost[y][x]=dis;
}
for(i=1;i<=n;i++) dist[i]=cost[1][i]; //dist[i]表示1为起点i为终点的边的权值
vis[1]=1;
dist[1]=0;
for(i=1;i<n;i++){
int min=1e9,k=-1;
for(j=1;j<=n;j++){
if(!vis[j]&&dist[j]<min){ //找到未访问 而且 距离已访问结点最短的结点
min=dist[j];
k=j;
}
}
vis[k]=1; //找到最优的结点，构成一条新的最优边
if(k!=-1){
sum=sum+dist[k];//总权值
for(j=1;j<=n;j++){
if(!vis[j]&&dist[j]>cost[k][j]){ //更新权值
dist[j]=cost[k][j];
}
}
}
}
cout<<sum<<endl;
return 0;
}
我这两个算法总是搞混，下面是区别
Prim (普里姆)算法和Dijkstra (迪杰斯特拉)的区别
(1)分析对象不同,前者为无向图,后者为有向图。
(2)连通的顶点不同，前者连通所有顶点，且总的代价最低，后者为单源点多目标点最短路径，所求得的是两顶点之间代价最小。
(3)普里姆算法生成最小生成树需重复n-1次，迪杰斯特拉算法则需重复n-2次。