Little Q’s factory recently purchased m pieces of new equipment, labeled by 1,2,⋯,m.
There are n workers in the factory, labeled by 1,2,⋯,n. Each worker can be assigned to no more than one piece of equipment, and no piece of equipment can be assigned to multiple workers. If little Q assigns the i-th worker to the j-th piece of equipment, he will need to pay aij2+bij+ci dollars.
Now please for every k(1⩽k⩽n)find k, pairs of workers and pieces of equipment, then assign workers to these pieces of equipment, such that the total cost for these k workers is minimized.
Input
The first line of the input contains a single integer T(1⩽T⩽10), the number of test cases.
For each case, the first line of the input contains two integers n and m(1⩽n⩽50,n⩽m⩽108), denoting the number of workers and the number of pieces of equipment.
Each of the following n lines contains three integers ai,bi and ci $(1\leqslant a_i\leqslant 10, $$−10^8\leqslant b_i\leqslant 10^8, 0\leqslant c_i\leqslant 10^{16}, b^2_i\leqslant 4a_ic_i)$, denoting a worker.
Output
For each test case, output a single line containing n integers, the k-th (1⩽k⩽n) of which denoting the minimum possible total cost for k pairs of workers and pieces of equipment.
Sample Input
1
3 5
2 3 10
2 -3 10
1 -1 4
Sample Output
4 15 37
Idea
对于第 i 个工人,其费用为一个二次函数 f(i,j)=aij2+bij+ci,根据二次函数的性质,可在区间 [1,m] 的最小值附近,求出 f(i,j) 的在 i 已知时的前 n 小值;我们暂且记录下前 n 小值所取到的工具编号 j1,j2,⋯,jn,因为这些工具可能在最终的方案中被选取。
对于可能在最终方案中被选取的工具,其编号较大,需要进行离散化操作,记离散化后有 num 个备选工具。
工人和工具的关系类似二分图,设工人为左部 V1,备选工具为右部 V2。设超级源点 s,编号为 0;超级汇点 t,编号为 n+num;编号为 1∼n 的节点为左部的工人,编号为 n+1∼num+n 的节点为右部的备选工具。由于要找到最小费用的完备匹配,因此设所有边的容量为 1;而费用只会在匹配时产生,即 V1 和 V2 间的边才会产生费用,其余边的费用为 0。从 s 向 n 个工人连边,容量为 1,费用为 0。遍历 n 个工人,对于每一个工人,向 num 件工具连边,为保证一个工人只能使用一件工具,容量为 1,费用则为 f(i,j)。对于 num 件工具,分别向 t 连边,容量为 1,费用为 0。由于每个工人都会产生 n 个备选工具,那么有 n⩽num⩽n2,即 ∣V1∣⩽∣V2∣;并且,任意 k 个工人都至少有 k 个备选工具;根据 Hall 定理,必然存在完备匹配。由于每个工人都选取其前 n 个费用最小的工具,因此这个完备匹配是费用最小的。
运行 MCMF 算法,用 SPFA 进行 n 次增广,就能依次得到工人数量为 k=1,2,⋯,n 时的最小费用完备匹配。时间复杂度为 O(n5)。