题解：P10768 「CROI · R2」落月摇情
FanMingxuan · · 题解
P10768（贪心+分类讨论+多路归并优先队列）
题目大意：
给你
这
前置知识：多路归并优先队列
如果一个问题是由多种选择构成，并且要查询最优解，次优解等等，每种选择有多个决策，最终答案为所有决策取最小值获得，暴力将所有可能扔进优先队列会 TLE/MLE，这时候如果每种选择的决策是由单调性的那么就可以使用多路归并优先队列去优化决策。
例如：
如图所示，我们要求其中的前
思路分析：
要求图连通，并且让选取边权和最小。
这是一类套路性的问题，我们可以先求出最小生成树，然后把非树边贪心的从小到大加入。这时候我们观察特殊数据点，有一类数据是
注意到
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 的边我们连了两次，实际编写程序时连接一次即可。
至此，我们通过分类讨论写出了最小生成树，由于有排序，此时复杂度为
Part2. 加入剩余非树边
获得最小生成树后，我们只需要把剩余的
这时候我们想到多路归并优先队列，我们维护一个小根堆，对每个点都放入最小乘积，每次取出队头，然后把他的下一个决策放进去，若下一个决策和自己重合或者超出范围就直接丢弃，直至达成目标。
我们发现，若某个数是正数，他的决策位置必然是从小到大递增的。反之，如果是负数，他的决策位置必然是从大到小递减的。
时间复杂度
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。
完结撒花！