#P17962. Bipartite Graph Weighting Problem

Bipartite Graph Weighting Problem

Bipartite Graph Weighting Problem

给定一个二分图。左右两部各有 nn 个顶点,两部顶点分别编号为 11 到 nn。图中有 mm 条边,每条边连接一个左部顶点和一个右部顶点。

需要回答 qq 个相互独立的询问,每个询问给定三个整数 (a,b,k)(a,b,k)。

对于一个固定询问,所有顶点的权值初始均为 00。可以执行任意多次以下操作:

  • 任意选择左部顶点集合 SS(可以为空),以及一个正实数 p>0p>0。
  • 记 N(S)N(S) 为与 SS 中至少一个顶点相邻的全部右部顶点组成的集合。
  • 给 SS 中每个顶点的权值增加 a⋅pa\cdot p。
  • 给 N(S)N(S) 中每个顶点的权值增加 b⋅pb\cdot p。

设所有操作中选择的正实数依次为 p1,…,pℓp_1,\ldots,p_\ell,要求

∑i=1ℓpi≤1.\sum_{i=1}^{\ell}p_i\le1.

你需要选择这些操作,使左右两部全部顶点的权值总和至多为 kk,并在此条件下,让左部全部顶点的权值总和最大。

每个询问都从所有权值为 00 的状态独立开始。求每个询问的最大值。

输入格式

第一行一个整数 tt(1≤t≤10001\le t\le1000),表示测试用例数。

每个测试用例第一行三个整数 n,m,qn,m,q(1≤n≤20001\le n\le2000,0≤m≤1040\le m\le10^4,1≤q≤2⋅1051\le q\le2\cdot10^5)。

接下来 mm 行,每行两个整数 u,vu,v(1≤u,v≤n1\le u,v\le n),表示左部 uu 与右部 vv 之间有一条边。没有重边。

接下来 qq 行,每行三个整数 a,b,ka,b,k(0≤a,b≤1060\le a,b\le10^6,0≤k≤1090\le k\le10^9),描述一个询问。

一个输入文件中 ∑n≤2000\sum n\le2000,∑m≤104\sum m\le10^4,∑q≤2⋅105\sum q\le2\cdot10^5。

输出格式

对于每个询问,输出一行一个实数,表示左部权值总和的最大值。

设你的答案为 xx,标准答案为 yy,当

∣x−y∣max⁡(1,∣y∣)≤10−6\frac{|x-y|}{\max(1,|y|)}\le10^{-6}

时认为答案正确。

样例 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