CF1656F Parametric MST

给定一张 \(n\) 个点的无向完全图 \(K_n(t)\)，点 \(i\) 和点 \(j\) 之间的边的边权 \(w_{i,j}(t)\) 为 \(a_i\times a_j+t \times (a_i+a_j)\)，其中 \(t\) 为任意实数。

定义 \(f(t)\) 为 \(K_n(t)\) 的最小生成树的边权和。输出 \(f(t)\) 的最大值，无最大值则输出 INF 。

分析

首先将 \(a\) 从小到大排序，设 \(s\) 为 \(a\) 的前缀和
，确定 \(i\) 时，\(a_ia_j+t(a_i+a_j)=(t+a_i)a_j+ta_i\) 。

因为 \(ta_i\) 是个定值，所以只需考虑 \(t+a_i\) 的正负，若 \(t+a_i\) 为正则肯定贪心选择最小的 \(a_j\)，否则选择最大的 \(a_j\) 。所以，对于 \(t\) 非常大，若 \((a_1*(n-1)+s_n-s_1)>0\) 则为 \(INF\)，同理若 \(t\) 是非常小的负数，若 \((a_n*(n-1)+s_n-s_1)<0\) 则为 \(INF\)。

其它情况我们观察一下式子 \(w_{i,j}(t)=a_ia_j+t(a_i+a_j)=(a_i+t)(a_j+t)-t^2\)，令\(b_i=a_i+t\)，则权值为 \(w_{i,j}(t)=b_ib_j-t^2\)，令 \(w_{i,j}=b_ib_j\) 则 \(f(t)=mst-(n-1)t^2\) （ \(mst\) 为最小生成树权值和），对于所有的对于任意一个 \(t\)，一定满足 $ [1,i]\ b_i<0$ ，\([i+1,n]\ b_i>0\)，对于 $ b_i<0$ 我们将其和 \(max(b_i)\)) 相连，对于 $ b_i>0$ 我们将其和 \(min(b_i)\) 相连，这样求出来的就是最小值，通过枚举 \(t\) 求解即可。

发现 t 在 \([-a_{i+1},-a_i]\) 可以把这个范围内的 \(f(t)\) 表示成一个关于 \(t\) 的一次函数。这怎么理解呢？比如说，t 在 \([-a_{i+1},-a_i]\) 范围内，每次 \(+1\)，最小生成树选择的边是不会变的，则答案就会变化 \(\sum{a_i+a_j}-2\times t\times (n-1)\)，( \((i,j)\) 为选择的边)，显然 \(\sum{a_i+a_j}\) 的值不会变，所以为一次函数。所以，最大值肯定取在端点处，所以依次只要枚举 \(t=-a_i\) 的权值，再取个最大值就行了。

\(code\)

#include<bits/stdc++.h>
#define N 200005
#define int long long
using namespace std;
int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
int T,n;
int a[N],s[N];
signed main(){
	T=read();
	while(T--){
		n=read();
		for(int i=1;i<=n;++i) a[i]=read();
		sort(a+1,a+1+n);
		for(int i=1;i<=n;++i) s[i]=s[i-1]+a[i];
		if(s[n]-s[1]+a[1]*(n-1)>0||s[n-1]+a[n]*(n-1)<0){printf("INF\n");continue;}
		int ans=-1e18;
		for(int i=1;i<=n;++i){
			int t=-a[i];
			int maxn=a[n]+t,minn=a[1]+t;
			int ls=s[i]+i*t,rs=s[n]-s[i]+(n-i)*t;
			ans=max(ans,ls*maxn+rs*minn-minn*maxn-(n-1)*t*t);
		}
		printf("%lld\n",ans);
	}
	return 0;
}