还是畅通工程
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 20992 Accepted Submission(s): 9360
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 Huge input, scanf is recommended.
Hint
Hint Source
Recommend
JGShining
思路:Prim
代码:
#include#include #include #include #include using namespace std;const int MAXN = 10000;int map[110][110];int n;int the_last_flag;int the_last_sum;bool p[110];int pre[110];int dist[110];int first,end,cast,done;void Prim(int n,int dist[110],int map[110][110],int pre[110]){ int minn; for(int i = 2;i <= n;i ++) { p[i] = false; dist[i] = map[1][i]; pre[i] = 1; } dist[1] = 0; p[1] = true; for(int i = 1;i <= n - 1;i ++) { minn = MAXN; the_last_flag = 0; for(int j = 1;j <= n;j ++) { if(!p[j] && minn > dist[j]) { minn = dist[j]; the_last_flag = j; } } if(the_last_flag == 0) return ; p[the_last_flag] = true; for(int j = 1;j <= n;j ++) { if(!p[j] && map[the_last_flag][j] != MAXN && dist[j] > map[the_last_flag][j]) { dist[j] = map[the_last_flag][j]; pre[j] = the_last_flag; } } }}int main(){ while(scanf("%d",&n),n != 0) { for(int i = 1;i <= n;i ++) { for(int j = 1;j <= n;j ++) { if(i == j) map[i][j] = 0; else { map[i][j] = MAXN; } } } for(int i = 1;i <= ((n - 1) * n) / 2;i ++) { scanf("%d%d%d",&first,&end,&cast); map[first][end] = cast; map[end][first] = cast; } the_last_flag = 0; the_last_sum = 0; Prim(n,dist,map,pre); for(int i = 1;i <= n;i ++) the_last_sum += dist[i]; printf("%d\n",the_last_sum); } return 0;}