| 题目名称 | 1541. [Ural 1569] Iset塔上的网络 |
|---|---|
| 输入输出 | iset.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cstdio
于2014-03-06加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：10， 提交：48， 通过率：20.83% | ||||
 cstdio |
100 | 0.013 s | 0.41 MiB | C++ |
 ceerRep |
100 | 0.013 s | 0.41 MiB | C++ |
 confoo |
100 | 0.014 s | 0.36 MiB | C++ |
 Ostmbh |
100 | 0.015 s | 0.41 MiB | C++ |
 mikumikumi |
100 | 0.018 s | 0.33 MiB | C++ |
 _Itachi |
100 | 0.018 s | 0.33 MiB | C++ |
 St.Burning\ |
100 | 0.021 s | 0.41 MiB | C++ |
 KZNS |
100 | 0.056 s | 0.35 MiB | C++ |
 胡嘉兴 |
100 | 0.072 s | 0.40 MiB | C++ |
 The_Unbeatable |
100 | 0.119 s | 0.53 MiB | C++ |
| 关于 Iset塔上的网络 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
我肯定是假KZ了。。。。
| ||||
|
百度最小直径生成树
| ||||
|
传说中的bfs树
| ||||
|
只想说：不说什么了…
St.Burning\
2014-10-18 19:20
2楼
| ||||
|
评测插件的原理是floyd最短路然后枚举找直径，如果插件有问题找我
| ||||
【题目描述】
Iset塔（高度215米，叶卡捷琳堡第二高楼）很快就要投入运营了，但在建筑中还没有安装计算机网络。这个网络应该非常健壮，有许多的分叉。塔中有N个节点，它们应该被连接到网络中。计划用M条无向边连接这些节点，两个节点之间最多只有一条边。为了节省时间，决定只修建必须的N-1条边，而剩余的电线将在开业典礼后铺设。为了让网络高效，它必须满足一个额外条件：它节点之间的最大距离必须尽可能小。两个节点A,B之间的距离是A,B之间路径的边数。
【输入格式】
输入文件的第一行有两个整数N(2<=N<=100)和M(1<=M<=10000)。接下来的M行描述了最初计划的网络。每行有两个整数，即两个直接相连的节点。节点从1到N编号。假定这个网络是连通的，并且没有节点连接到自身。
【输出格式】
输出N-1行，即开业前必须铺设的网络（按照相同的格式）。
【样例输入】
4 4
1 2
2 3
2 4
3 4
【样例输出】
1 2
2 3
2 4
【提示】
对于30%的数据，1<=N<=10
对于100%的数据，范围如题中所示
【来源】
Problem Author: Sergey Pupyrev
Problem Source: The XIIth USU Programing Championship, October 6, 2007