首页 > 代码库 > HDOJ 1233 还是畅通工程
HDOJ 1233 还是畅通工程
来源: http://acm.hdu.edu.cn/showproblem.php?pid=1233
归类: 图论 、Prime算法
还是畅通工程
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 26037 Accepted Submission(s): 11608
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 5Huge input, scanf is recommended.HintHint
Source
浙大计算机研究生复试上机考试-2006年
题意 略。
题解: Prime 算法 无向稠密图,直接用链接矩阵存储~~空间利用率高,便于查找。然后直接套Prime模板就可以解决了。
AC代码:
#include<cstdio> #define INF 2147483647 const int Max=5000; bool pa[105],pb[105]; int n,sum,map[Max][Max],from,to,w,wage; void prime(){ int posb=n-1; while(posb){ int min=INF,tempa,tempb; for(int k=1;k<=n;k++) if(pa[k]) for(int i=1;i<=n;i++) if(~map[k][i]&&pb[i]&&min>map[k][i]){ min=map[k][i];tempa=k;tempb=i; } wage+=min; map[tempa][tempb]=-1;map[tempb][tempa]=-1; posb--; pa[tempb]=true; pb[tempb]=false; } } int main(){ while(scanf("%d",&n),n){ sum=n*(n-1)/2; wage=0; for(int i=1;i<=n;i++) { pb[i]=true;pa[i]=false; } pa[1]=true;pb[1]=false; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) map[i][j]=-1; //以上均为初始化 for(int i=0;i<sum;i++){ scanf("%d%d%d",&from,&to,&w); map[from][to]=w; map[to][from]=w; } //输入各辺长度 prime(); printf("%d\n",wage); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。