#P17962. Bipartite Graph Weighting Problem
Bipartite Graph Weighting Problem
Bipartite Graph Weighting Problem
给定一个二分图。左右两部各有 个顶点,两部顶点分别编号为 到 。图中有 条边,每条边连接一个左部顶点和一个右部顶点。
需要回答 个相互独立的询问,每个询问给定三个整数 。
对于一个固定询问,所有顶点的权值初始均为 。可以执行任意多次以下操作:
- 任意选择左部顶点集合 (可以为空),以及一个正实数 。
- 记 为与 中至少一个顶点相邻的全部右部顶点组成的集合。
- 给 中每个顶点的权值增加 。
- 给 中每个顶点的权值增加 。
设所有操作中选择的正实数依次为 ,要求
你需要选择这些操作,使左右两部全部顶点的权值总和至多为 ,并在此条件下,让左部全部顶点的权值总和最大。
每个询问都从所有权值为 的状态独立开始。求每个询问的最大值。
输入格式
第一行一个整数 (),表示测试用例数。
每个测试用例第一行三个整数 (,,)。
接下来 行,每行两个整数 (),表示左部 与右部 之间有一条边。没有重边。
接下来 行,每行三个整数 (,),描述一个询问。
一个输入文件中 ,,。
输出格式
对于每个询问,输出一行一个实数,表示左部权值总和的最大值。
设你的答案为 ,标准答案为 ,当
时认为答案正确。
样例 1
输入
2
5 8 3
1 2
1 3
2 4
2 5
3 1
3 3
4 2
5 4
1 3 5
2 1 2
5 2 3
2 3 3
1 2
1 1
2 1
1 0 2
0 2 2
3 1 4
输出
1.250000000000000
1.333333333333333
2.142857142857144
2.000000000000000
0.000000000000000
3.000000000000000