[HDOJ1233]还是畅通工程

摘要:
省政府“畅通工程”的目标是实现省内任意两个村庄之间的道路交通,要求铺设道路的总长度最小。每个测试用例的第一行给出了村庄的数量N;以下N(N-1)/2条线对应于村庄之间的距离。每条线给出一对正整数,这是两个村庄的数量和两个村庄之间的距离。为了简单起见,村庄的编号从1到N。输出对于每个测试用例,输出1行中道路的最小总长度。SampleInput312113232441211341412332423450SampleOutput35HintHintHugeinput,scanfis推荐。来源浙江大学计算机研究生复试-2006和搜索+最小生成树,使用STL的优先级队列来关注数组扩展,代码如下:1#include<iostream>2#include<queue>3#include<csdio>4#include<cs ring>5#define MAXN10000067 usingspacestd;89intpre[MAXN];10structNode{11intx;12inty;13intd;14friendboolopperb.d;16}17};1819intfind{20returnx==pre[x]?
还是畅通工程

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 30793    Accepted Submission(s): 13822


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
Hint
Hint
Huge input, scanf is recommended.
 
Source
浙大计算机研究生复试上机考试-2006年
 
并查集+最小生成树,使用STL的优先队列(STL优先队列介绍:http://blog.csdn.net/morewindows/article/details/6976468)
注意数组开大点,代码如下:
 
[HDOJ1233]还是畅通工程第1张[HDOJ1233]还是畅通工程第2张
 1 #include <iostream>
 2 #include <queue>
 3 #include <cstdio>
 4 #include <cstring>
 5 #define MAXN 100000
 6 
 7 using namespace std;
 8 
 9 int pre[MAXN];
10 struct Node {
11     int x;
12     int y;
13     int d;
14     friend bool operator < (Node a, Node b) {
15         return a.d > b.d;
16     }
17 };
18 
19 int find(int x) {
20     return x == pre[x] ? x : pre[x] = find(pre[x]);
21 }
22 
23 int unite(int x, int y) {
24     x = find(x);
25     y = find(y);
26     if(x != y) {
27         pre[x] = y;
28         return 1;
29     }
30     return 0;
31 }
32 
33 int main() {
34     int N, n, ans;
35     while(~scanf("%d", &N) && N != 0) {
36         ans = 0;
37         n = N * (N - 1) / 2;
38         priority_queue<Node> q;
39         Node tmp;
40         for(int i = 1; i <= n; i++) {
41             scanf("%d %d %d", &tmp.x, &tmp.y, &tmp.d);
42             pre[i] = i;
43             q.push(tmp);
44         }
45         N = N - 1;
46         while(N) {
47             tmp = q.top();
48             q.pop();
49             if(unite(tmp.x, tmp.y)) {
50                 N--;
51                 ans += tmp.d;
52             }
53         }
54         printf("%d
", ans);
55     }
56     return 0;
57 }
View Code

免责声明:文章转载自《[HDOJ1233]还是畅通工程》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇[模拟]位运算实现四则运算POJ3468 A Simple Problem with Integers下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

随便看看

CentOS7 添加FTP用户并设置权限

step 1 安装配置Vsftp服务器 一、配置防火墙,开启FTP服务器需要的端口 CentOS 7.0默认使用的是firewall作为防火墙,这里改为iptables防火墙。 1、关闭firewall: systemctl stop firewalld.service#停止firewall systemctl disable f...

Connect to URL and dump webpage in Groovy Stack Overflow

Connect to URL and dump webpage in Groovy - Stack Overflow 5down voteaccepted This is a good example http://groovy.codehaus.org/Simple+file+download+from+URL Basically you w...

关于函数返回值的几种情况

在一个函数的内部,return的时候返回的都是一个拷贝,不管是变量、对象还是指针都是返回拷贝,但是这个拷贝是浅拷贝。 1.如果返回一个基本类型的变量,比如: int a; a = 5; return a; 那么就会a的一个拷贝,即5返回,然后a就被销毁了。尽管a被销毁了,但它的副本5还是成功地返回了,所以这样做没有问题。 2.但是对于非动态分配(new...

mchaput / whoosh / wiki / Home — Bitbucket

mchaput / whoosh / wiki / Home — Bitbucket About Whoosh Whoosh is a fast, featureful full-text indexing and searching libraryimplemented in pure Python. Programmers can use it to...

MySQL 自增ID 规格严格

http://hi.baidu.com/517898291/item/9cac18066030cac6905718e0 http://jiangshuiy.iteye.com/blog/751060 Sina 转载: MySQL: Get next AUTO_INCREMENT value from/fortable Note to self: To g...

Linux时区、时间的更改

Linux 时钟分为系统时钟(System Clock)和硬件(Real Time Clock ,简称RTC )时钟。系统时钟是指当前Linux Kernel中的时钟,而硬件时钟则是主板上由电池供电的时钟,这个硬件时钟可以在BIOS中进行设置。当Linux 启动时,硬件时钟会去读取系统时钟的设置,然后系统时钟就会独立于硬件运作。Linux中的所有命令(包括函...