有些点城镇已经连通好了 但是我们在做的时候是求剩下的连通起来要花多少钱
我们可以依然把这些已经连通好的边放进我们将要连通的所有边中 不过花费是0
这样依旧求出的是最短路 注意找的是最短路
#include<stdio.h>
#include<stdlib.h>
int map[105][105];
struct haha
{
int view1;
int view2;
int value;
}e[30000+5];
int parent[10005];
int cmp(const void *a,const void *b)
{
return (*(struct haha *)a).value-(*(struct haha *)b).value;
}
int get_root(int x)
{
return x==parent[x]?x:get_root(parent[x]);
}
int join(int x,int y)
{
int root1,root2;
root1=get_root(x);
root2=get_root(y);
// printf("root1=%d root2=%d\n",root1,root2);
if(root1==root2) return 0;
else parent[root1]=root2;
return 1;
}
int main()
{
int i,j,n,k,x,y,c,ans;
while(scanf("%d",&n)!=EOF)
{
c=1;ans=0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&map[i][j]);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(map[i][j])
{
e[c].view1=i;
e[c].view2=j;
e[c].value=map[i][j];
c++;
}
}
for(i=0;i<=102;i++)
parent[i]=i;
scanf("%d",&k);
i=c;
for(c;c<i+k;c++)
{
scanf("%d %d",&x,&y);
e[c].view1=x;
e[c].view2=y;
e[c].value=0;
}
// printf("%d",c);
qsort(e+1,c-1,sizeof(e[0]),cmp);
// for(i=1;i<c;i++)
// printf("value=%d\n",e[i].value);
// printf("c=%d\n",c);
for(i=1;i<c;i++)
{
// printf("i=%d:",i);
if(join(e[i].view1,e[i].view2))
{
ans=ans+e[i].value;
}
}
printf("%d\n",ans);
}
return 0;
}
关于PAT(Programming Ability Test)培训的报名~
分享到:
相关推荐
杭电ACM课件2014版之 (HDUACM201403版_06)并查集(最小生成树)
(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树
HDU的ACM,非常的好 涉及了很多算法,例如二分匹配、博弈、组合、最小生成树、搜索、动态规划、贪心算法
很实用的算法讲解,hdu的lcy老师讲解,还不错!!
hdu ACM代码 每种算法都有分类 大三了,没有时间弄ACM,这些要删了
hdu动态规划算法集锦
hdu 1166线段树代码
acm 技术大牛 课件 HDU 自学必备课件 全套齐全 (lecture_01)初识ACM (lecture_02)简单数学题 (lecture_03)递推求解 (lecture_04)动态规划(1)_ (lecture_05)计算几何基础_ (lecture_06)母函数 (lecture_...
杭州电子科技大学oj平台上的第1010题,是关于搜索的题目,很不错的题
八数码的A*算法~不是很高效,但是很适合刚刚学这个算法的朋友们
杭电ACM 培训课件,包括各种常用的算法,并结合例题详细的讲解,对提高算法思想用很大帮助
算法-数塔(HDU-2084).rar
hdu 1166线段树
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
算法-超级楼梯(HDU-2040)(包含源程序).rar
HDU的一题........HDU DP动态规