HDU-1233-还是畅通工程(并查集)

时间:2022-08-23 10:49:45
题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=1233
题目很简单(最小生成树) #include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std; struct node
{

int
x,y,d;
}
s[]; int father[];
int
sum; bool cmp(const node &a,const node &b)
{

return
a.d<b.d;
}
int Find(int x)
{

if
(x==father[x]) return x;
father[x]=Find(father[x]);
return
father[x];
}
void Union(int x,int y,int d)
{

x=Find(x);
y=Find(y);
if
(x!=y)
{

father[x]=y;
sum=sum+d;
}
}
int main(void)
{

int
n,m,i,j,k,l;
while
(scanf("%d",&n)==&&n)
{

m=n*(n-)/;
for
(i=;i<m;i++)
scanf("%d%d%d",&s[i].x,&s[i].y,&s[i].d);
sort(s,s+m,cmp);
for
(i=;i<=n;i++)
father[i]=i;
sum=;
for
(i=;i<m;i++)
{

Union(s[i].x,s[i].y,s[i].d);
}

printf("%d\n",sum);
}

return
;
}

HDU-1233-还是畅通工程(并查集)的更多相关文章

  1. hdu 1233 还是畅通工程 并查集or最小生成树

    某省调查乡村交通状况,得到的统计表中列出了任意两村庄间的距离.省*“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可),并要求铺设的公路 ...

  2. HDU&period;1233 还是畅通工程(Prim)

    HDU.1233 还是畅通工程(Prim) 题意分析 首先给出n,代表村庄的个数 然后出n*(n-1)/2个信息,每个信息包括村庄的起点,终点,距离, 要求求出最小生成树的权值之和. 注意村庄的编号从 ...

  3. hdu 1233 还是畅通工程 (最小生成树)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1233 还是畅通工程 Time Limit: 4000/2000 MS (Java/Others)    ...

  4. HDU 1233 还是畅通工程(Kruskal算法)

    题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1233 还是畅通工程 Time Limit: 4000/2000 MS (Java/Others)   ...

  5. hdu 1863 畅通工程 &lpar;并查集&plus;最小生成树&rpar;

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1863 畅通工程 Time Limit: 1000/1000 MS (Java/Others)    M ...

  6. HDU - 1232 畅通工程-并查集模板

    某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇.省*“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可). ...

  7. &lt&semi;hdu - 1232&gt&semi; 畅通工程 并查集问题 (注意中的细节)

    本题链接:http://acm.hdu.edu.cn/showproblem.php?pid=1232  结题思路:因为题目是汉语的,那我就不解释题意了,要求的是最少建设的道路,我们可以用并查集来做这 ...

  8. HDU 1232 畅通工程&lpar;并查集)

    畅通工程 Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Problem Des ...

  9. HDU 1232 &lpar;畅通工程&rpar; 并查集经典模板题

    Problem Description 某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇.省*"畅通工程"的目标是使全省任何两个城镇间都可以实现交通 ...

  10. hdu 1863 畅通工程 &lpar;并查集 、 kruskal&rpar;

    畅通工程Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submiss ...

随机推荐

  1. ios常见的页面传值方式

    iOS页面间的传值细分有很多种,基本的传值方式有三种:委托Delegate传值.通知NSNotification传值.Block传值,其他在项目中可能会遇到的还有:UserDefault或文件方式传值 ...

  2. linux文件描述符open file descriptors与open files的区别

    一个文件被打开,也可能没有文件描述符,比如current working diretories,memory mapped files and executable text files ;losf可 ...

  3. http&colon;&sol;&sol;runjs&period;cn&sol;

    http://runjs.cn/ RunJS - 在线编辑.展示.分享.交流你的 JavaScript 代码

  4. &lbrack;转载&rsqb;C&num;读写配置文件&lpar;XML文件&rpar;

    .xml文件格式如下 [xhtml] view plaincopy <?xml version="1.0" encoding="utf-8"?> & ...

  5. javaScript滚动新闻

    <!DOCTYPE HTML> <html> <head> <meta http-equiv="Content-Type" content ...

  6. 避免循环做SQL操作

    经常犯的错误是把一个SQL 操作放置到一个循环中, 这就导致频繁的访问数据库,更重要的是, 这会直接导致脚本的性能低下.以下的例子, 你能够把一个循环操作重置为一个单一的SQL语句. foreach ...

  7. Python中&ast;和&ast;&ast;的作用&lpar;课堂小结&rpar;

    以前自学没注意过参数的传导中*和**的用法,这次趁着上课了解了一下,顺便写个随笔记一下. 1.打包用法 在参数传导中*args是不定长参数,传入的参数是不限制个数的,比如 def bdc(*args) ...

  8. Framework连接oracle数据库以及Cognos服务器出现错误

     1:Framework连接oracle数据库时出现下面错误信息 环境: win2008R2 cognos10.2.1, 服务器上已经安装oracle11.2 content manager连接的也是 ...

  9. BZOJ 3343:教主的魔法(分块)

    [题目链接] http://www.lydsy.com/JudgeOnline/problem.php?id=3343 [题目大意] 给出一个数列,有区间加法操作,询问区间大于等于c的数字个数 [题解 ...

  10. jQuery 2&period;1&period;4版本的源码分析

    jQuery 2.1.4版本的源码分析 jquery中获取元素的源码分析 jQuery.each({// 获取当前元素的父级元素 parent: function(elem) { var parent ...