#P9642. [IPSC2008]Expected Cost
[IPSC2008]Expected Cost
题目描述
有 个村庄和 条可以修建的双向道路。第 条道路连接村庄 ,实际造价独立地从闭区间 均匀抽取。当 时,造价固定为 。
实际造价全部确定后,从这些道路中选择能连接所有村庄且总造价最低的方案。求该最小总造价的期望。如果无论造价如何都无法连接所有村庄,输出 -1。
输入格式
第一行一个整数 ,表示测试用例数。每组输入前可能有空行。
每组第一行两个整数 ,分别表示村庄数和候选道路数。接下来 行,每行四个整数 ,其中 ,。
输出格式
每组输出一行。若图不连通,输出 -1。否则把期望写为最简分数 A/B,不含空格。即使分母为 1,也要输出。
样例
4
3 2
0 1 0 9
1 2 10 11
4 2
0 1 10 11
1 2 10 12
3 3
0 1 0 1
1 2 2 2
0 2 3 3
3 3
0 1 0 1
1 2 0 1
0 2 0 1
15/1
-1
5/2
3/4
第一组的两条道路都必须修建。第二组有一个孤立村庄。第三组恒取前两条道路。第四组的最优值是三个独立均匀随机数中较小两个之和。
站内评测数据
原赛直接向选手提供 E1、E2 两个输入文件。本站使用相同的两套输入,其结构如下。
| 数据 | 的上界 | 的上界 | 造价端点 | |
|---|---|---|---|---|
| E1 | 23 | 47 | 46 | 所有边均为 |
| E2 | 8 | 1000 | 999 |
对连通图作点双连通分解,单独处理桥。E1 的每个块最多有 15 条边。E2 中,在同一块内按各边造价端点划分阈值区间。对相邻端点 ,缩并所有 的边,忽略所有 的边和缩并后成为自环的边。剩余仍不确定的边最多 9 条。
题面据 IPSC 2008 Problem E 改写,源材料采用 CC BY-SA 3.0。