#P9642. [IPSC2008]Expected Cost

    ID: 6258 传统题 5000ms 512MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-点双连通分量可撤销并查集全子集枚举期望的尾积分公式期望线性性分段多项式普通多项式乘法有理数精确运算

[IPSC2008]Expected Cost

题目描述

有 NN 个村庄和 MM 条可以修建的双向道路。第 ii 条道路连接村庄 xi,yix_i,y_i,实际造价独立地从闭区间 [li,ui][l_i,u_i] 均匀抽取。当 li=uil_i=u_i 时,造价固定为 lil_i。

实际造价全部确定后,从这些道路中选择能连接所有村庄且总造价最低的方案。求该最小总造价的期望。如果无论造价如何都无法连接所有村庄,输出 -1。

输入格式

第一行一个整数 TT,表示测试用例数。每组输入前可能有空行。

每组第一行两个整数 N,MN,M,分别表示村庄数和候选道路数。接下来 MM 行,每行四个整数 xi,yi,li,uix_i,y_i,l_i,u_i,其中 0≤xi,yi<N0\le x_i,y_i<N,0≤li≤ui0\le l_i\le u_i。

输出格式

每组输出一行。若图不连通,输出 -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 两个输入文件。本站使用相同的两套输入,其结构如下。

数据 TT NN 的上界 MM 的上界 造价端点
E1 23 47 46 所有边均为 [0,1][0,1]
E2 8 1000 999 0≤li≤ui≤9990\le l_i\le u_i\le999

对连通图作点双连通分解,单独处理桥。E1 的每个块最多有 15 条边。E2 中,在同一块内按各边造价端点划分阈值区间。对相邻端点 L<RL<R,缩并所有 ui≤Lu_i\le L 的边,忽略所有 li≥Rl_i\ge R 的边和缩并后成为自环的边。剩余仍不确定的边最多 9 条。

IPSC 2008 原题与原赛输入

题面据 IPSC 2008 Problem E 改写,源材料采用 CC BY-SA 3.0。