题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1233
还是畅通工程
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 26151 Accepted Submission(s):
11660
Problem Description
某省调查乡村交通状况,得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可),并要求铺设的公路总长度为最小。请计算最小的公路总长度。
Input
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100
);随后的N(N-1)/2行对应村庄间的距离,每行给出一对正整数,分别是两个村庄的编号,以及此两村庄间的距离。为简单起见,村庄从1到N编号。
当N为0时,输入结束,该用例不被处理。
当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
这是一个简单的最小生成树,第一次做,没有深刻的理解,自我感觉和dijkstra没有什么太大的本质区别,总之又是一种找最短路的很好的方法吧,值得参考~
1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4 int node[110],map[110][110],n; 5 const int INF=9999999; 6 7 void prim() 8 { 9 int vis[110]= {0}; 10 int sum=0,Min,tm=1,m; 11 node[tm]=0; 12 vis[tm]=1;//cout<<n<<endl; 13 for (int k=2; k<=n; k++) 14 { 15 16 Min=INF; 17 for (int i=1; i<=n; i++) 18 if (!vis[i]) 19 { 20 if (node[i]>map[tm][i]) 21 node[i]=map[tm][i]; 22 if (Min>node[i]) 23 { 24 Min=node[i]; 25 m=i; 26 } 27 } 28 vis[m]=1; 29 sum+=Min; 30 tm=m; 31 } 32 printf ("%d ",sum); 33 } 34 35 int main () 36 { 37 while (cin>>n&&n) 38 { 39 for(int i=1; i<=n; i++) 40 { 41 node[i]=INF; 42 } 43 for (int i=1; i<=n*(n-1)/2; i++) 44 { 45 int a,b,c; 46 cin>>a>>b>>c; 47 map[a][b]=map[b][a]=c; 48 } 49 prim(); 50 } 51 return 0; 52 }
第二种方法哈,也就是并查集+最小生成树了~~哇哈哈
详见代码。
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 using namespace std; 5 int father[110],sum; 6 struct node 7 { 8 int s,d,f; 9 } p[5010]; 10 11 bool cmp(const node &a,const node &b) 12 { 13 return a.f<b.f; 14 } 15 16 void set(int n) 17 { 18 for (int i=1; i<=n; i++) 19 father[i]=i; 20 } 21 22 int find(int a) 23 { 24 if (father[a]==a) 25 return a; 26 return father[a]=find(father[a]); 27 } 28 29 void Union(int x,int y,int z) 30 { 31 x=find(x); 32 y=find(y); 33 if (x!=y) 34 { 35 sum+=z; 36 father[x]=y; 37 } 38 } 39 40 int main () 41 { 42 int n; 43 while (cin>>n&&n) 44 { 45 sum=0; 46 set(n); 47 for (int i=1; i<=n*(n-1)/2; i++) 48 cin>>p[i].s>>p[i].d>>p[i].f; 49 sort(p+1,p+n*(n-1)/2+1,cmp); 50 for (int i=1; i<=n*(n-1)/2; i++) 51 { 52 Union(p[i].s,p[i].d,p[i].f); 53 } 54 printf ("%d ",sum); 55 } 56 return 0; 57 }