HDU-1233 还是畅通工程 (prim 算法求最小生成树)
prim 算法求最小生成树
还是畅通工程
Time Limit: 4000/2000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 20712Accepted Submission(s): 9213
Problem Description
某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。
Input
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。 当N为0时，输入结束，该用例不被处理。
Output
对每个测试用例，在1行里输出最小的公路总长度。
Sample Input
3
1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0
Sample Output
3
5
Hint
Hint
Huge input, scanf is recommended.
Source
浙大计算机研究生复试上机考试-2006年
Recommend
JGShining
1、ssh-login 一键密码加密登录工具
2、数据挖掘：同义词的那些事
3、PostGIS官方教程汇总目录
4、python simple wsgi web_server
5、Oracle的分区打点
1 #include<stdio.h> 2 #include<string.h> 3 #define max 100000000 4 int map[101][101],sum,min;// map[i][j] 记录从点 i 到点 j 的距离 ！ 5 int main() 6 { 7 int n,m,i,x,y,dis,j,flag,visit[101]; 8 while(~scanf("%d",&n)&&n!=0) 9 { 10 11 m=(n*(n-1))/2; 12 memset(map, 0, sizeof(map));//数组清零 13 memset(visit,0,sizeof(visit)); 14 for(i=0;i<m;i++) 15 { 16 scanf("%d%d%d",&x,&y,&dis); 17 map[x-1][y-1]=map[y-1][x-1]=dis; 18 } 19 for(i=0;i<n;i++) 20 map[i][i]=max;//建图完成 ！ 21 visit[0]=1; sum=0; 22 for ( i=1; i<n; i++)//prim 算法求最小生成树 23 { 24 min= 10000000; 25 for ( j=0; j<n; j++) 26 { 27 if (!visit[j] && map[0][j] < min) 28 { 29 min = map[0][j]; 30 flag = j; 31 } 32 } 33 sum += min; 34 visit[flag] = 1; 35 for ( j=0; j<n; j++) 36 { 37 if (!visit[j] && map[0][j] > map[flag][j]) 38 { 39 map[0][j] = map[flag][j]; 40 } 41 } 42 } 43 printf("%d\n",sum); 44 } 45 return 0; 46 } 47 48
prim写成函数的方式，更容易理解。
1 #include<stdio.h> 2 int map[101][101],visit[101]; 3 int length[101]; 4 int getmin(int n) 5 { 6 int i,min; 7 for(i=1;i<=n;i++) 8 { 9 if(visit[i]==0) 10 { 11 min=i; 12 break; 13 } 14 } 15 for(i++;i<=n;i++) 16 { 17 if(visit[i]==0&&length[min]>length[i]) 18 min=i; 19 } 20 return min; 21 } 22 int prim(int n) 23 { 24 int i,j; 25 int min; 26 int sum; 27 for(i=1;i<=n;i++) 28 { 29 visit[i]=0; 30 length[i]=map[1][i]; 31 } 32 visit[1]=1; 33 sum=0; 34 for(i=2;i<=n;i++) 35 { 36 min=getmin(n); 37 visit[min]=1; 38 sum+=length[min]; 39 for(j=1;j<=n;j++) 40 { 41 if(visit[j]==0) 42 { 43 if(map[min][j]<length[j]) 44 { 45 length[j]=map[min][j]; 46 } 47 } 48 } 49 } 50 return sum; 51 } 52 int main() 53 { 54 int n, m; 55 int i; 56 int min; 57 int u, v, cost; 58 while (scanf("%d", &n) != EOF && n != 0) 59 { 60 m = n * (n - 1) / 2; 61 for (i = 0; i <= n; i++) 62 map[i][i] = 0; 63 for (i = 0; i < m; i++) 64 { 65 scanf("%d%d%d", &u, &v, &cost); 66 map[u][v] = cost; 67 map[v][u] = cost; 68 69 } 70 min = prim(n); 71 printf("%d\n", min); 72 } 73 return 0; 74 }
浓缩版：
#include<stdio.h> #include<string.h> #define MAX 100000 int map[101][101],v[101]; int prim(int n)//最好的prim的模板。 { int k[510],i,j; int min,sum=0,flag,count=1; memset(k,0,sizeof(k)); memset(v,0,sizeof(v)); for(i=1;i<=n;i++) k[i]=map[1][i]; for(i=2;i<=n;i++) { min=MAX; for(j=2;j<=n;j++) { if(min>k[j]&&v[j]==0) { min=k[j]; flag=j; } } sum+=min; v[flag]=1; for(j=1;j<=n;j++) if(v[j]==0&&k[j]>map[flag][j]&&flag!=j) k[j]=map[flag][j]; } return sum; } int main() { int n,m,i,j,p,q,r,min; while(~scanf("%d",&n)&&n!=0) { m=n*(n-1)/2; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if(i==j) map[i][j]=0; else map[i][j]=MAX; } for(i=0;i<m;i++) { scanf("%d%d%d",&p,&q,&r); map[p][q]=map[q][p]=r; } min=prim(n); printf("%d\n",min); } return 0; }优质内容筛选与推荐>>
1、ssh-login 一键密码加密登录工具
2、数据挖掘：同义词的那些事
3、PostGIS官方教程汇总目录
4、python simple wsgi web_server
5、Oracle的分区打点