这题就是最小生成树,不过样例输出看了好久,一看DISCUSS才知道,这题是SPJ,答案不唯一,不必管样例
下面Kruskal+并查集
一次AC!!
Network
Time Limit:1000MS |
|
Memory Limit:30000K |
Total Submissions:7721 |
|
Accepted:2835 |
|
Special Judge |
Description
Andrew is working as system administrator and is planning to establish a new network in his company. There will be N hubs in the company, they can be connected to each other using cables. Since each worker of the company must have access to the whole network, each hub must be accessible by cables from any other hub (with possibly some intermediate hubs).
Since cables of different types are available and shorter ones are cheaper, it is necessary to make such a plan of hub connection, that the maximum length of a single cable is minimal. There is another problem — not each hub can be connected to any other one because of compatibility problems and building geometry limitations. Of course, Andrew will provide you all necessary information about possible hub connections.
You are to help Andrew to find the way to connect hubs so that all above conditions are satisfied.
Input
The first line of the input contains two integer numbers: N - the number of hubs in the network (2 <= N <= 1000) and M - the number of possible hub connections (1 <= M <= 15000). All hubs are numbered from 1 to N. The following M lines contain information about possible connections - the numbers of two hubs, which can be connected and the cable length required to connect them. Length is a positive integer number that does not exceed 106. There will be no more than one way to connect two hubs. A hub cannot be connected to itself. There will always be at least one way to connect all hubs.
Output
Output first the maximum length of a single cable in your hub connection plan (the value you should minimize). Then output your plan: first output P - the number of cables used, then output P pairs of integer numbers - numbers of hubs connected by the corresponding cable. Separate numbers by spaces and/or line breaks.
Sample Input
4 6
1 2 1
1 3 1
1 4 2
2 3 1
3 4 1
2 4 1
Sample Output
1
4
1 2
1 3
2 3
3 4
分享到:
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1705139
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
北大POJ初级-所有题目AC代码+解题报告
北大POJ3733-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ3373-Changing Digits【DFS+强剪枝】 解题报告+AC代码
NULL 博文链接:https://200830740306.iteye.com/blog/603493
poj2492 A Bug's Life并查集应用的扩展,希望可以给大家带来用处
POJ2186-Popular Cows 【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
NULL 博文链接:https://128kj.iteye.com/blog/1704752
利用并查集判断环路,以及快速排序计算最小生成树
NULL 博文链接:https://128kj.iteye.com/blog/1707218
先利用prim算法求出最小生成树,然后通过往MST里加边来判断新生成的最小生成树是否具有最小的权值,POJ上The Unique MST(1679)题是要求判断最小生成树是否唯一,此题其实根本不用这样做,但是为了练习球次小生成树...
POJ 1988 并查集。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
1.把自己的污水排到河里V 2.把自己的污水送到右边> 3.把自己的污水送到左边
北大POJ初级-简单搜索 解题报告+AC代码
这份代码用C++实现了经典算法并查集,来源于poj题目1182
北大POJ初级题-数据结构:解题报告+AC代码
北大POJ2187-Beauty Contest 解题报告+AC代码