Codeforces 1656 F. Parametric MST

题目链接

Problem

给定$n$个参数$a_1,a_2,\cdots,a_n$，对于$n$个点的无向完全图，令$K_n(t)$表示图上的最小生成树，对于图上任意两点$i,j$的边边权为$w_{ij}(t) = a_ia_j + ta_ia_j$，令$f(t)$表示$K_n(t)$的边权和，$t$可取任意实数，判断函数$f(t)$是否有上界，如果有输出上界。

Data Range

$2\leq n\leq 2\cdot 10^5$

$-10^6 \leq a_i\leq 10^6$

Solution

可以将边权进行一个很显然的变换:$w_{ij}(t) = (a_i + t) \cdot ( a_j + t) - t ^ 2$。

于是每个点的参数可以视为$b_i = a_i + t$。

对于一个给定的$t$，每条边的边权后半部分$t^2$视为一个常数，每个点将视为有一个参数为$b_i = a_i + t$，边权$w_{ij} = b_ib_j$。

对$b$数组从小到大排序，可以发现：

1. 如果所有的$b_i$符号相同，显然对应的最小生成树为1号节点与其他所有点连边
2. 如果$b_1 b_n < 0$；生成的最小生成树第一条边为1号点连接n号节点，对于其他节点，如果$b_i$为负，则连接n号节点；如果$b_i$为正，则连接1号节点，由此构成最小生成树(MST)。

可以发现，只有当$b$数组中正数、负数个数发生改变时，才有可能改变最小生成树的连接方式，也就是说，$f(t)$是一个分段函数。

继续进行观察当$t\in[-a_{i + 1}, -a_i]$时，考虑$w_{ij}(t) = a_ia_j+ ta_ia_j$是关于$t$的一次函数，所有$f(t)$是一个一次函数，只有在$-a_{i + 1}$或者$-a_i$时才有可能取到极值。

那么就只要枚举$t=a_i$，并进行计算即可，具体计算公式见代码。

Code

/*************************************************************************
    > File Name: 1.cpp
    > Author: Knowledge-Pig
    > Mail: 925538513@qq.com
    > Blog: https://www.cnblogs.com/Knowledge-Pig/
    > Created Time: 2022年03月31日 星期四 15时08分13秒
************************************************************************/

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define LL long long
#define pb push_back
#define fi first
#define se second
#define pr pair<int,int>
#define mk(a,b) make_pair(a,b)
#define endl '\n'
using namespace std;
const int maxx = 3e5 + 10;
LL n, a[maxx], sum[maxx];
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.in", "r", stdin);
	freopen("output.out", "w", stdout);
#endif
	int T; cin >> T;
	while(T--){
		cin >> n;
		for(int i = 1; i <= n; ++i) cin >> a[i];
		sort(a + 1, a + n + 1);
		for(int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + a[i];
		if(sum[n] + (n - 2) * a[n] < 0) cout << "INF" << endl;
		else if(sum[n] + (n - 2) * a[1] > 0) cout << "INF" << endl;
		else{
			LL ans = -1e18;
			for(int i = 1; i <= n; ++i){
				LL tmp = sum[i] * a[n] + (sum[n] - sum[i]) * a[1] - a[1] * a[n];
				tmp -= a[i] * (i * a[n] + (n - i) * a[1] + sum[n] - a[1] - a[n]);
				ans = max(ans, tmp);
			}
			cout << ans << endl;
		}
	}
	return 0;
}