传送门 ↬\looparrowright

Problem Description

Little Q’s factory recently purchased mm pieces of new equipment, labeled by 1,2,⋯ ,m1,2,\cdots,m.
There are nn workers in the factory, labeled by 1,2,⋯ ,n1,2,\cdots,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 ii-th worker to the jj-th piece of equipment, he will need to pay aij2+bij+cia_ij^2+b_ij+c_i dollars.
Now please for every kk (1⩽k⩽n)(1\leqslant k\leqslant n)find kk, pairs of workers and pieces of equipment, then assign workers to these pieces of equipment, such that the total cost for these kk workers is minimized.

Input

The first line of the input contains a single integer TT (1⩽T⩽10)(1\leqslant T\leqslant 10), the number of test cases.
For each case, the first line of the input contains two integers nn and mm (1⩽n⩽50(1\leqslant n\leqslant 50,, n⩽m⩽108)n\leqslant m\leqslant 10^8), denoting the number of workers and the number of pieces of equipment.
Each of the following nn lines contains three integers ai,bia_i,b_i and cic_i $(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 nn integers, the kk-th (1⩽k⩽n)(1\leqslant k\leqslant n) of which denoting the minimum possible total cost for kk 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

对于第 ii 个工人，其费用为一个二次函数 f(i,j)=aij2+bij+cif(i,j)=a_ij^2+b_ij+c_i，根据二次函数的性质，可在区间 [1,m][1,m] 的最小值附近，求出 f(i,j)f(i,j) 的在 ii 已知时的前 nn 小值；我们暂且记录下前 nn 小值所取到的工具编号 j1,j2,⋯ ,jnj_1,j_2,\cdots,j_n，因为这些工具可能在最终的方案中被选取。
对于可能在最终方案中被选取的工具，其编号较大，需要进行离散化操作，记离散化后有 numnum 个备选工具。
工人和工具的关系类似二分图，设工人为左部 V1V_1，备选工具为右部 V2V_2。设超级源点 ss，编号为 00；超级汇点 tt，编号为 n+numn+num；编号为 1∼n1\sim n 的节点为左部的工人，编号为 n+1∼num+nn+1\sim num+n 的节点为右部的备选工具。由于要找到最小费用的完备匹配，因此设所有边的容量为 11；而费用只会在匹配时产生，即 V1V_1 和 V2V_2 间的边才会产生费用，其余边的费用为 00。从 ss 向 nn 个工人连边，容量为 11，费用为 00。遍历 nn 个工人，对于每一个工人，向 numnum 件工具连边，为保证一个工人只能使用一件工具，容量为 11，费用则为 f(i,j)f(i,j)。对于 numnum 件工具，分别向 tt 连边，容量为 11，费用为 00。由于每个工人都会产生 nn 个备选工具，那么有 n⩽num⩽n2n\leqslant num\leqslant n^2，即 ∣V1∣⩽∣V2∣|V_1|\leqslant|V_2|；并且，任意 kk 个工人都至少有 kk 个备选工具；根据 Hall\text{Hall} 定理，必然存在完备匹配。由于每个工人都选取其前 nn 个费用最小的工具，因此这个完备匹配是费用最小的。
运行 MCMF\text{MCMF} 算法，用 SPFA\text{SPFA} 进行 nn 次增广，就能依次得到工人数量为 k=1,2,⋯ ,nk=1,2,\cdots,n 时的最小费用完备匹配。时间复杂度为 O(n5)O(n^5)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: HDU 6767
Date: 8/10/2020
Description: Minimum-cost Flow
*******************************************************************/
#include<iostream>
#include<cstring>
#include<vector>
#include<utility>
#include<queue>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long ll;
const int N=3003;
const ll inf=0x3f3f3f3f3f3f3f3f;
int _;
struct E
{
	int to;
	int cap;
	ll cost;
	int Next;
}edge[N*1000];
int head[N],tot;
int incf[N],pre[N];
ll dis[N];
bool inqueue[N];
int m,n,num;
int s,t;
ll a[N],b[N],c[N];
vector<int>selected;
void init();
inline void add_edge(int,int,int,ll);
bool SPFA();
void MCMF();
int main()
{
	for(cin>>_;_;_--)
	{
		selected.clear();
		scanf("%d%d",&n,&m);
		int i,j;
		for(i=1;i<=n;i++) scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
		for(i=1;i<=n;i++)
		{
			vector<pair<int,ll>>expense;
			//抛物线最低点
			int limit=max(1,(int)(-b[i]/(2*a[i])));
			//左右两边个各n个值
			for(j=limit;j>=1;j--)
			{
				ll id=j;
				ll expenditure=a[i]*id*id+b[i]*id+c[i];
				expense.push_back(make_pair(id,expenditure));
				if(limit-j+1==n) break;
			}
			for(j=limit+1;j<=m;j++)
			{
				ll id=j;
				ll expenditure=a[i]*id*id+b[i]*id+c[i];
				expense.push_back(make_pair(id,expenditure));
				if(j-limit==n) break;
			}
			//按照费用升序排列
			sort(expense.begin(),expense.end(),
			[](const pair<int,ll>& x,const pair<int,ll>& y)
			{return x.second<y.second;});
			//取前n个
			for(j=0;j<n;j++) selected.push_back(expense[j].first);
		}
		//排序去重 离散化
		sort(selected.begin(),selected.end());
		selected.erase(unique(selected.begin(),selected.end()),selected.end());
		init();
		for(i=1;i<=n;i++) add_edge(s,i,1,0);
		for(i=1;i<=n;i++)
		{
			for(j=0;j<num;j++)
			{
				ll expenditure=selected[j]*a[i]*selected[j]+b[i]*selected[j]+c[i];
				add_edge(i,j+1+n,1,expenditure);
			}
		}
		for(i=1;i<=num;i++) add_edge(i+n,t,1,0);
		MCMF();//n次增广
	}
	return 0;
}
void init()
{
	tot=1;
	memset(head,-1,sizeof(head));
	s=0;
	num=selected.size();
	t=n+num+1;
}
inline void add_edge(int u,int v,int cap,ll cost)
{
	tot++;
	edge[tot].to=v;
	edge[tot].cap=cap;
	edge[tot].cost=cost;
	edge[tot].Next=head[u];
	head[u]=tot;
	tot++;
	edge[tot].to=u;
	edge[tot].cap=0;
	edge[tot].cost=-cost;
	edge[tot].Next=head[v];
	head[v]=tot;
}
bool SPFA()
{
	queue<int>q;
	memset(dis,inf,sizeof(dis));
	memset(inqueue,0,sizeof(inqueue));
	q.push(s);
	dis[s]=0;
	inqueue[s]=1;
	incf[s]=0x3f3f3f3f;
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		inqueue[x]=0;
		for(register int i=head[x];~i;i=edge[i].Next)
		{
			if(!edge[i].cap) continue;//剩余容量为0，不在残量网络中。
			int y=edge[i].to;
			if(dis[y]>dis[x]+edge[i].cost)
			{
				dis[y]=dis[x]+edge[i].cost;//松弛操作
				incf[y]=min(incf[x],edge[i].cap);//最小剩余容量
				pre[y]=i;//记录前驱
				if(!inqueue[y])
				{
					inqueue[y]=1;
					q.push(y);
				}
			}
		}
	}
	if(dis[t]==inf) return 0;//汇点不可达，已经求出最大流
	else return 1;
}
void MCMF()
{
	ll maxflow,mincost;
	maxflow=mincost=0;
	for(register int k=1;k<=n;k++)
	{
		if(SPFA())
		{
			int x=t;
			//沿着前驱倒着走增广路
			while(x!=s)
			{
				int y=pre[x];
				edge[y].cap-=incf[t];
				edge[y^1].cap+=incf[t];
				x=edge[y^1].to;
			}
			maxflow+=incf[t];
			mincost+=dis[t]*incf[t];
		}
		printf("%lld",mincost);
		putchar(k==n?'\n':' ');
	}
}

Postscript

少用几个 long long 会快很多。