继续畅通工程
Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7025Accepted Submission(s): 2952
Problem Description
省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可)。现得到城镇道路统计表,表中列出了任意两城镇间修建道路的费用,以及该道路是否已经修通的状态。现请你编写程序,计算出全省畅通需要的最低成本。
Input
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 1< N < 100 );随后的 N(N-1)/2 行对应村庄间道路的成本及修建状态,每行给4个正整数,分别是两个村庄的编号(从1编号到N),此两村庄间道路的成本,以及修建状态:1表示已建,0表示未建。
当N为0时输入结束。
Output
每个测试用例的输出占一行,输出全省畅通需要的最低成本。
Sample Input
31 2 1 01 3 2 02 3 4 031 2 1 01 3 2 02 3 4 131 2 1 01 3 2 12 3 4 10
Sample Output
310
#include<stdio.h>
#include<string.h>
int map[103][103];
int min[100+5];
int used[100+5];
int prim(int n)
{
int i,j,m,rem,ans;
memset(used,0,sizeof(used));//初始化 表示每个点都还没用用过
used[1]=1;
for(i=1;i<=n;i++)
min[i]=map[1][i];//初始化
ans=0;
for(i=1;i<=n;i++)
{
m=999999999;
for(j=1;j<=n;j++)
{
if(used[j]==0&&m>min[j])
{
m=min[j];//寻找min数组中边权最小的并入树中
rem=j;//记录最小的位置
}
}
if(m!=999999999)
ans+=m;
used[rem]=1;
for(j=1;j<=n;j++)
if(!used[j]&&map[rem][j]<min[j])
min[j]=map[rem][j];
}
return ans;
}
int main()
{
int n,i,j,k,flag,n1,n2;
while(scanf("%d",&n)&&n)
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
map[i][j]=999999999;//初始每个点之间的路径都很大
for(i=1;i<=n*(n-1)/2;i++)
{
scanf("%d %d %d %d",&n1,&n2,&k,&flag);
if(flag) map[n1][n2]=map[n2][n1]=0;//n2n1 n1n2都要赋值
else map[n1][n2]=map[n2][n1]=k;
}
printf("%d\n",prim(n));
}
return 0;
}
分享到:
相关推荐
杭电ACM课件2014版之 (HDUACM201403版_06)并查集(最小生成树)
(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树
算法-畅通工程(HDU-1232)(包含源程序).rar
HDU的ACM,非常的好 涉及了很多算法,例如二分匹配、博弈、组合、最小生成树、搜索、动态规划、贪心算法
算法-畅通工程续(HDU-1874)(包含源程序).rar
很实用的算法讲解,hdu的lcy老师讲解,还不错!!
hdu ACM代码 每种算法都有分类 大三了,没有时间弄ACM,这些要删了
hdu动态规划算法集锦
题目链接题目意思有n个城镇,编号为0~n-1,m条道路,从一个城镇到另一个城镇有多条路,现在问你从一个城镇到另一个城镇的最短距离是多少。其中要注意的是,城镇之间
hdu 1166线段树代码
acm 技术大牛 课件 HDU 自学必备课件 全套齐全 (lecture_01)初识ACM (lecture_02)简单数学题 (lecture_03)递推求解 (lecture_04)动态规划(1)_ (lecture_05)计算几何基础_ (lecture_06)母函数 (lecture_...
杭州电子科技大学oj平台上的第1010题,是关于搜索的题目,很不错的题
杭电ACM 培训课件,包括各种常用的算法,并结合例题详细的讲解,对提高算法思想用很大帮助
八数码的A*算法~不是很高效,但是很适合刚刚学这个算法的朋友们
算法-数塔(HDU-2084).rar
hdu 1166线段树
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告