题面:
题意:
给定n个二次函数 f(i),保证他们的最小值都大于0,且开口向上。
从 [1,m]中任选k个整数点(这些点互不相同) p[i],从n个二次函数中任选k个二次函数 f(i),对于 k∈[i,n] 输出 ∑i=1kf(p[i])的最小值。
题解:
二次函数 f(i)的最小值一定在其对称轴附近取得。观察发现我们只需要每个二次函数的前n小即可。
建立一个源点S,汇点T。
源点S向每个二次函数连一条费用为0,流量为1的边。
每个二次函数向使其前n小的点连一条费用为 f(p[i]),流量为1的边。
所有出现过能使某个二次函数取到前n小的点向汇点连一条费用为0,流量为1的边。
我们增广n次找到流量为 1,2...n的最小费用流即可。
官方题解:
代码:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#include<list>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
//#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=998244353;
const double eps=1e-1;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=5200;
const int maxp=1100;
const int maxm=500100;
const int up=100000;
int head[maxn],ver[maxn<<1],edge[maxn<<1],nt[maxn<<1];
ll cost[maxn<<1],d[maxn],ans[maxn];
int incf[maxn],pre[maxn],ha[maxn],tot=1,cnt=0,pos=0;
int s,t;
map<int,int>mp;
vector<int>vc;
ll a[maxn],b[maxn],c[maxn];
void init(int n)
{
memset(head,0,sizeof(head));
tot=1;
cnt=n;
mp.clear();
}
int id(int x)
{
if(mp.count(x)) return mp[x];
else return mp[x]=++cnt;
}
void add(int x,int y,int z,ll c)
{
ver[++tot]=y,edge[tot]=z,cost[tot]=c;
nt[tot]=head[x],head[x]=tot;
ver[++tot]=x,edge[tot]=0,cost[tot]=-c;
nt[tot]=head[y],head[y]=tot;
}
bool spfa(void)
{
queue<int>q;
memset(d,0x3f,sizeof(d));
memset(ha,0,sizeof(ha));
q.push(s);
d[s]=0;
ha[s]=1;
incf[s]=inf;
while(q.size())
{
int x=q.front();
ha[x]=0;
q.pop();
for(int i=head[x];i;i=nt[i])
{
if(!edge[i]) continue;
int y=ver[i];
if(d[y]>d[x]+cost[i])
{
d[y]=d[x]+cost[i];
incf[y]=min(incf[x],edge[i]);
pre[y]=i;
if(!ha[y]) ha[y]=true,q.push(y);
}
}
}
if(d[t]==lnf) return false;
return true;
}
void update(void)
{
int x=t;
while(x!=s)
{
int i=pre[x];
edge[i]-=incf[t];
edge[i^1]+=incf[t];
x=ver[i^1];
}
}
void getans(int n)
{
for(int i=1;i<=n;i++)
{
spfa();
update();
ans[i]=ans[i-1]+d[t];
}
}
ll fi(int i,int x)
{
return a[i]*x*x+b[i]*x+c[i];
}
bool cmp(const int &a,const int &b)
{
return fi(pos,a)<fi(pos,b);
}
int main(void)
{
int tt;
scanf("%d",&tt);
while(tt--)
{
int n,m;
scanf("%d%d",&n,&m);
init(n);
for(int i=1;i<=n;i++)
{
scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
vc.clear();
pos=i;
for(int j=max(1ll,-b[i]/(2*a[i])-n-5),now=0;j<=m&&now<=2*n+10;j++,now++)
vc.pb(j);
sort(vc.begin(),vc.end(),cmp);
for(int j=0;j<n;j++)
add(i,id(vc[j]),1,fi(pos,vc[j]));
}
s=cnt+1,t=s+1;
for(int i=1;i<=n;i++)
add(s,i,1,0);
for(int i=n+1;i<=cnt;i++)
add(i,t,1,0);
getans(n);
for(int i=1;i<=n;i++)
{
if(i!=1) putchar(' ');
printf("%lld",ans[i]);
}
putchar('\n');
}
return 0;
}