http://poj.org/problem?id=2421
无向图的最小生成树 Kruskal算法
Constructing Roads
Time Limit:2000MS |
|
Memory Limit:65536K |
Description
There are N villages, which are numbered from 1 to N, and you should build some roads such that every two villages can connect to each other. We say two village A and B are connected, if and only if there is a road between A and B, or there exists a village C such that there is a road between A and C, and C and B are connected.
We know that there are already some roads between some villages and your job is the build some roads such that all the villages are connect and the length of all the roads built is minimum.
Input
The first line is an integer N (3 <= N <= 100), which is the number of villages. Then come N lines, the i-th of which contains N integers, and the j-th of these N integers is the distance (the distance should be an integer within [1, 1000]) between village i and village j.
Then there is an integer Q (0 <= Q <= N * (N + 1) / 2). Then come Q lines, each line contains two integers a and b (1 <= a < b <= N), which means the road between village a and village b has been built.
Output
You should output a line contains an integer, which is the length of all the roads to be built such that all the villages are connected, and this value is minimum.
Sample Input
3
0 990 692
990 0 179
692 179 0
1
1 2
Sample Output
179
分享到:
相关推荐
北大POJ1724-ROADS 解题报告+AC代码
西北工业大学POJ试题C++答案代码+课程设计
北大POJ1207-The 3n + 1 problem 解题报告+AC代码
poj2492 A Bug's Life并查集应用的扩展,希望可以给大家带来用处
POJ-2870 Light Up + DFS(1级DFS+1级DFS) + Python - 思维导图 链接:https://blog.csdn.net/xxdragon126/article/details/122095922?spm=1001.2014.3001.5501
POJ1724-ROADS 测试数据。数据来源:CEOI 1998 Round II
poj 2749 Building roads.md
1129 1149 1154 1165 1182 1185 1190 1191 1201 1251 1273 1275 1276 1286 1322 1338 1363 1364 1401 1456 1459 1564 1579 1637 1657 1658 1679 ...2104 2112 2115 2186 2255 2352 2369 2406 2409 2421 2479 2480 2498
POJ 1988 并查集。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
NULL 博文链接:https://128kj.iteye.com/blog/1707218
北大POJ3411-Paid Roads【class】 解题报告+AC代码
北大POJ初级-简单搜索 解题报告+AC代码
这份代码用C++实现了经典算法并查集,来源于poj题目1182
并查集基础 acm 算法 poj oi 并查集基础.ppt
poj 1611 The Suspects 代码 并查集的应用
数据结构并查集的相关资料,包括几篇并查集的论文,还有POJ上面几道关于并查集的题目的源代码
POJ1089 并查集可以解决 并查集加路径压缩
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
北大POJ初级-所有题目AC代码+解题报告