自动搬运

查看原文

来自洛谷，原作者为

	FanMingxuan 时光荏苒，小 S 和小 Y 也会散去。而我们和一个人保持连接的方式就是记住，仅此而已。—— 《NOI 2024 Day1 T1》

搬运于2025-08-24 23:01:02，当前版本为作者最后更新于2024-07-13 20:36:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P10768（贪心+分类讨论+多路归并优先队列）

题目大意：

给你 $n$ 个点，每个点有点权。

这 $n$ 个点构成一张完全图，每条边的边权定义为两端点权值之积，你需要在这张图中取 $m$ 条边，使得整张图连通，最小化边权之和。

前置知识：多路归并优先队列

如果一个问题是由多种选择构成，并且要查询最优解，次优解等等，每种选择有多个决策，最终答案为所有决策取最小值获得，暴力将所有可能扔进优先队列会 TLE/MLE，这时候如果每种选择的决策是由单调性的那么就可以使用多路归并优先队列去优化决策。

例如：

如图所示，我们要求其中的前 $k$ 大的数，我们发现，如果某一行前面的数没有被选择，那么后面的必然不会被选。那么我们可以先把第一列的四个数放入优先队列并注明来源，每次取出队头，并将其后面的决策放入优先队列，直至选出 $k$ 个。

思路分析：

要求图连通，并且让选取边权和最小。

这是一类套路性的问题，我们可以先求出最小生成树，然后把非树边贪心的从小到大加入。这时候我们观察特殊数据点，有一类数据是 $m = n - 1$ 的，很显然，这道题考察点之一就是如何构建这张图的最小生成树。所以先考虑如何构建最小生成树。

注意到 $n \le 1 \times 10^6$，并且是一张完全图，常见的最小生成树算法如 Kruskal，Prim 都无法应对。

Part1. 求解最小生成树

我们发现，这道题的边权比较特殊，定义为两端点的点权之积，那么我们可以从这里入手，我们可以先对所有点进行一次排序。

考虑对所有数的正负分类讨论：

• 若所有数均为正数：如 1 2 3 4 5 6，不难看出，只需要让除 1 以外的所有点向 1 连一条边即可，即向点权最小的点连边。

• 若所有数均为负数：如 -6 -5 -4 -3 -2 -1，也不难看出，只需要让除 -1 以外的所有点向 -1 连一条边即可，即向点权最大的点连边。

• 若序列中既有正数，又有负数：如 -2 -1 0 1 2 3，因为异号两个数相乘一定是最优的，那么对于其中的负数 -2 -1 ，我们将其向最大的正数 3 连一条边，而对于非负数 0 1 2 3 我们将其向最小的负数 -2 连一条边，我们发现 -2 到 3 的边我们连了两次，实际编写程序时连接一次即可。

至此，我们通过分类讨论写出了最小生成树，由于有排序，此时复杂度为 $O(n \log n)$，瓶颈在排序。

Part2. 加入剩余非树边

获得最小生成树后，我们只需要把剩余的 $m - (n - 1)$ 条非树边贪心的加入即可，但是我们不能把剩下的边一次性全部存入优先队列然后取前 $m - (n - 1)$ 条。

这时候我们想到多路归并优先队列，我们维护一个小根堆，对每个点都放入最小乘积，每次取出队头，然后把他的下一个决策放进去，若下一个决策和自己重合或者超出范围就直接丢弃，直至达成目标。

我们发现，若某个数是正数，他的决策位置必然是从小到大递增的。反之，如果是负数，他的决策位置必然是从大到小递减的。

时间复杂度 $O(m \log n)$。

Part3. 剩余问题

• 我们需要判断一下重边，当我们每加入一条边，我们需要存一下这条边是否被选取，防止重复选择。我们可以使用把 $u$,$v$ 作为一个状态，并把状态存入 unordered_map 即可。

• 本题卡常，注意代码实现。

• 不妨设 $n$,$m$ 同阶，总时间复杂度为 $O(n \log n)$。

代码实现：

#include<bits/stdc++.h>
using namespace std;
const int N = 3000005; 

struct node{
	long long w; //点权 
	int id; //便于排序后找到原位置 
}a[N];

namespace Graph{
	struct edge{
		int u;
		int v;
	}e[N];
	int cur = 0;
	
	void addedge(int u,int v){
		e[++ cur].u = u;
		e[cur].v = v;
	}
	
	void print(){
		for(int i = 1;i <= cur;++ i){
			printf("%d %d\n",e[i].u,e[i].v);
		}
	}
} //链式前向星 

struct data{
	long long w; //代价 
	int first; //从哪个点出发 
	int current; //当前决策位置 
	int delta; //表示下一个决策的方向 
	
	friend bool operator<(const data& A,const data& B){
		return A.w > B.w; //优先队列维护小根堆 
	}
}; 

int main(){
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i = 1;i <= n;++ i){
		scanf("%lld",&a[i].w);
		a[i].id = i;
	}
	long long ans = 0;
	sort(a + 1,a + n + 1,[](const node& A,const node& B) -> bool const { return A.w < B.w; }); //先排序 
	
	unordered_map<unsigned long long,bool> used; //某条边是否已经选取 
	//这里存边规则为：
	//设小编号为 u，大编号为 v，那么就给 (u << 32) | v 这一状态打上标记 
	if(a[1].w < 0 && a[n].w > 0){ //有正有负 
		for(int i = 2;i < n;++ i){
			if(a[i].w < 0){ //负连最大 
				ans += a[i].w * a[n].w;
				Graph::addedge(a[i].id,a[n].id);
				int u = min(i,n);//小连大 
				int v = max(i,n);
				used[((unsigned long long)u << 32) | v] = true;
			}
			else{ //正连最小 
				ans += a[i].w * a[1].w;
				Graph::addedge(a[i].id,a[1].id);
				int u = min(i,1);//小连大 
				int v = max(i,1);
				used[((unsigned long long)u << 32) | v] = true;
			}
		}
		//最后只处理一次两端连边 
		ans += a[1].w * a[n].w;
		Graph::addedge(a[1].id,a[n].id);
		int u = min(1,n);
		int v = max(1,n);
		used[((unsigned long long)u << 32) | v] = true;
	}
	else if(a[1].w >= 0){ //全正 
		for(int i = 2;i <= n;++ i){ //全连最小 
			ans += a[i].w * a[1].w;
			Graph::addedge(a[i].id,a[1].id);
			int u = min(i,1);//小连大 
			int v = max(i,1);
			used[((unsigned long long)u << 32) | v] = true;
		}
	}
	else{ //全负 
		for(int i = 1;i < n;++ i){ //全连最大 
			ans += a[i].w * a[n].w;
			Graph::addedge(a[i].id,a[n].id);
			int u = min(i,n);//小连大 
			int v = max(i,n);
			used[((unsigned long long)u << 32) | v] = true;
		}
	}
	m -= (n - 1); //计算还需要补充几条边 
	priority_queue<data> q;
	for(int i = 1;i <= n;++ i){
		if(a[i].w > 0 && i != n) q.push({a[i].w * a[i + 1].w,i,i + 1,1}); //{代价，出发点，最优决策，下一个决策的方向}
		else{
			if(i == n) q.push({a[i].w * a[n - 1].w,i,n - 1,-1}); //特判一下最后一个点，最优决策不能和自己重合 
			else q.push({a[i].w * a[n].w,i,n,-1});
		}
	}
	while(m){
		data p = q.top();
		q.pop();
		long long w = p.w;
		int u = p.first;
		int v = p.current;
		int d = p.delta;
		int uu = min(u,v); //小连大 
		int vv = max(u,v);
		if(!used[((unsigned long long)uu << 32) | vv]){ //如果这条边未被使用就加入 
			used[((unsigned long long)uu << 32) | vv] = true;
			Graph::addedge(a[u].id,a[v].id);
			ans += w;
			m --; //补充上了一条 
		}
		if(d == 1){ //如果下一个决策向右 
			if(v == n) continue; //下一个决策会超出范围 直接丢弃 
			if(v + 1 == u) v ++; //下一个决策和自己重叠 再向右移动一个 
		}
		else{ //如果下一个决策向左 
			if(v == 1) continue; //下一个决策会超出范围 直接丢弃 
			if(v - 1 == u) v --; //下一个决策和自己重叠 再向左移动一个 
		}
		if(d == 1 && v == n) continue; //下一个决策会超出范围 直接丢弃 
		if(d == -1 && v == 1) continue; //同上 
		q.push({a[u].w * a[v + d].w,u,v + d,d}); //加入下一个决策 
	}
	printf("%lld\n",ans);
	Graph::print(); //打印构建的图 
	return 0;
}

后记：

细节有点多，需要仔细实现。

不知是哪个蒟蒻赛时没实现完，赛后 20 分钟直接 AC。

完结撒花！