还是畅通工程

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 52869    Accepted Submission(s): 23982 Problem Description 某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。   Input 测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。 当N为0时，输入结束，该用例不被处理。   Output 对每个测试用例，在1行里输出最小的公路总长度。   Sample Input 31 2 11 3 22 3 441 2 11 3 41 4 12 3 32 4 23 4 50   Sample Output 35 Hint Hint Huge input, scanf is recommended.

方法一（prim算法）；

普利姆（Prime）算法（只与顶点相关）

 

算法描述：

普利姆算法求最小生成树时候，和边数无关，只和定点的数量相关，所以适合求稠

 

密网的最小生成树，时间复杂度为O（n*n）。

算法过程：

1.将一个图的顶点分为两部分，一部分是最小生成树中的结点（A集合），另一部分

 

是未处理的结点（B集合）。

2.首先选择一个结点，将这个结点加入A中，然后，对集合A中的顶点遍历，找出A中

 

顶点关联的边权值最小的那个（设为v），将此顶点从B中删除，加入集合A中。

3.递归重复步骤2，直到B集合中的结点为空，结束此过程。

4.A集合中的结点就是由Prime算法得到的最小生成树的结点，依照步骤2的结点连接

 

这些顶点，得到的就是这个图的最小生成树。

#include<iostream> using namespace std; int map[101][101],dis[101]; bool book[101]; #define INF 999999 void prim(int n){ for(int i = 1;i <= n;i++) dis[i] = map[i][1]; int min,temp; book[1] = true;//1为起点 int sum = 0; for(int i = 2;i <= n;i++){ min = INF,temp = i; for(int j = 2;j <= n;j++){ if(!book[j] && dis[j] < min){ min = dis[j]; temp = j; } } book[temp] = true;//将该点加入已经添加的队列 sum += min; for(int j = 2;j <= n;j++){ if(dis[j]>map[temp][j]){ dis[j] = map[temp][j]; } } } printf("%d\n",sum); } int main(){ // freopen("input.txt","r",stdin); int a,b,c,n; while(scanf("%d",&n)!=EOF&&n){ for(int i = 1;i <= n;i++){ map[i][i] = 0; book[i] = false; } for(int i = 0;i < n*(n-1)/2;i++){ scanf("%d%d%d",&a,&b,&c); map[a][b]=map[b][a] = c; } prim(n); } return 0; }

方法二（kruskal 算法)

算法过程：

1.将图各边按照权值进行排序

2.将图遍历一次，找出权值最小的边，（条件：此次找出的边不能和已加入最小生成

 

树集合的边构成环），若符合条件，则加入最小生成树的集合中。不符合条件则继

 

续遍历图，寻找下一个最小权值的边。

3.递归重复步骤1，直到找出n-1条边为止（设图有n个结点，则最小生成树的边数应

 

为n-1条），算法结束。得到的就是此图的最小生成树。

#include<iostream> #include<algorithm> #include<cstring> #include<vector> using namespace std; #define N 5000 struct node{ int s,e,dis; }temp,v[N]; int pre[110]; void init(int n){ for(int i = 1;i <= n;i++) pre[i] = i; } int find(int root){ while(root != pre[root]) root = pre[root]; return root; } void join(int a,int b){ int x = find(a); int y = find(b); if(x != y) pre[x] = y; } bool cmp(node a,node b){ return a.dis < b.dis; } int main(){ int n; // freopen("input.txt","r",stdin); while(scanf("%d",&n) != EOF&&n){ int sum = 0; for(int i = 0;i < n*(n-1)/2;i++){ scanf("%d%d%d",&v[i].s,&v[i].e,&v[i].dis); } init(n); sort(v,v+(n*(n-1)/2),cmp); for(int i = 0;i < n*(n-1)/2;i++){ int x = find(v[i].s); int y = find(v[i].e); if(x != y){ sum += v[i].dis; join(v[i].s,v[i].e); } } printf("%d\n",sum); } return 0; }