| 比赛场次 | 147 |
|---|---|
| 比赛名称 | 20120708 |
| 比赛状态 | 已结束比赛成绩 |
| 开始时间 | 2012-07-08 08:00:00 |
| 结束时间 | 2012-07-08 12:00:00 |
| 开放分组 | 全部用户 |
| 注释介绍 | 2012暑假培训A班 |
| 题目名称 | 最小最大生成树 |
|---|---|
| 输入输出 | mstmn.in/out |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试点数 | 10 简单对比 |
| 用户 | 结果 | 时间 | 内存 | 得分 |
|---|---|---|---|---|
 ZhouHang |
AAAAAAAAAA | 0.648 s | 22.06 MiB | 100 |
 czp |
AAWAWAAAAA | 0.527 s | 2.68 MiB | 80 |
 Czb。 |
AAWWWWWWWW | 0.003 s | 0.29 MiB | 20 |
 Makazeu |
AAWWWWWWWW | 0.003 s | 0.29 MiB | 20 |
 Citron酱 |
WAWWWTTATT | 4.089 s | 6.62 MiB | 20 |
 CC |
AATTTTTTTT | 8.001 s | 0.29 MiB | 20 |
 zhangchi |
AATTTTTTTT | 8.023 s | 3.56 MiB | 20 |
 IMSL77 |
AWTTTTTTTT | 8.006 s | 12.60 MiB | 10 |
 SnowDancer |
C | 0.000 s | 0.00 MiB | 0 |
 isabella |
WWWWWWWWWW | 0.740 s | 14.78 MiB | 0 |
 fuhao |
WWWWWWWWWW | 0.815 s | 6.72 MiB | 0 |
-
【题目描述】
给定一个边带正权的连通无向图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