| 题目名称 | 856. 最小最大生成树 |
|---|---|
| 输入输出 | mstmn.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 sywgz
于2012-07-07加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：50， 提交：166， 通过率：30.12% | ||||
 stdafx.h |
100 | 0.391 s | 8.70 MiB | C++ |
 rvalue |
100 | 0.432 s | 21.57 MiB | C++ |
 HouJikan |
100 | 0.453 s | 0.85 MiB | C++ |
 czp |
100 | 0.604 s | 2.68 MiB | Pascal |
 乌龙猹 |
100 | 0.615 s | 9.70 MiB | C++ |
 哒哒哒哒哒！ |
100 | 0.626 s | 7.45 MiB | C++ |
 isabella |
100 | 0.640 s | 2.76 MiB | Pascal |
 zys |
100 | 0.692 s | 20.32 MiB | C++ |
|
Go灬Fire |
100 | 0.709 s | 28.47 MiB | C++ |
|
fuhao |
100 | 0.728 s | 21.83 MiB | Pascal |
| 本题关联比赛 | |||
| 20120708 | |||
| 关于 最小最大生成树 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
本机最后一个点0.3s不到，评测蜜汁超时，exm??
感觉cogs服务器运行这么久需要维护了233。  kito
2016-11-07 21:45
3楼
| ||||
|
。。。明白了，，
应该跑两次最小割。。。  Sky_miner
2016-10-09 07:55
2楼
| ||||
|
ISAP就是有效率
虽然写跪了N次QAQ  | ||||
-
【题目描述】
给定一个边带正权的连通无向图G=(V,E)，其中N=|V|, M=|E|，N个点从1到N依次编号，给定三个正整数u, v 和L (u≠v)，假设现在加入一条边权为L的边(u,v)，那么需要删掉最少多少条边，才能够使得这条边既可能出现在最小生成树上，也可能出现在最大生成树上？
【输入格式】
第一行包含用空格隔开的两个整数，分别为N和M；
接下来M行，每行包含三个正整数u, v和w表示图G存在一条边权为w的边(u,v)。
最后一行包含用空格隔开的三个整数，分别为u, v 和L；
数据保证图中没有自环。
【输出格式】
输出一行一个整数表示最少需要删掉的边的数量。
【样例输入】
3 2
3 2 1
1 2 3
1 2 2
【样例输出】
1
【样例说明】
我们只需把边(1,2)删除即可，删除并加入新边之后，图中的生成树唯一。
【数据规模和约定】
对于20%的数据满足N≤10，M≤20，L≤20；
对于50%的数据满足N≤300，M≤3000，L≤200；
对于100%的数据满足N≤20000，M≤200000，L≤20000。
【时限】
2s