题解：P10768 「CROI · R2」落月摇情

· · 题解

昨夜闲潭梦落花，可怜春半不还家。

江水流春去欲尽，江潭落月复西斜。

Solution P10768

::::info[Problem 1]{open} 这 m 条边的构成是什么？ ::::

::::success[Solution to Problem 1] 首先，m 条边一定是：原图的 MST 与剩下的边里面选 m-(n-1) 条。

证明是显然的：你要保证所有点都联通，所以你选择一个 MST。现在联通了，那你贪心的选择最小的加进去就行。 ::::

::::info[Problem 2] 如何求 MST？ ::::

::::success[Solution to Problem 2] 不难发现：

解决了 MST 问题。 ::::

::::info[Problem 3] 如何往上面加非 MST 边？ ::::

::::success[Solution to Problem 3]

很显然可以把所有边都算一遍排个序，但是复杂度 \operatorname{O}(n^2)，会爆炸。

你可以先对 a 排序，然后维护一个堆。

设 p_i 为排序之后对应位置为 i 的点。

那么你会发现：如果某个点 k 权值 >0，则如果 (p_1,k) 还没有被计算，(p_2,k) 进入这个堆是无意义的，因为 w_{(p_2,k)}>w_{(p_1,k)}，我们在算到 (p_1,k) 的时候再把 (p_2,k) 塞进去就行了。

同理，小于 0 的时候，就是从 (p_n,k) 开始处理，如果处理到了就把 (p_{n-1},k) 塞进去。

这样你只会处理 m 次加边操作，复杂度 \operatorname{O}(m\log n)。 ::::

::::error[小问题] 两步中，MST 中的边可能会被第二步也处理到。加上 MST 中的边也可能发生重复（例如 a=\{-1,1\}，那么处理 1 时会处理 (1,2)，处理 2 时处理的还是 (1,2)，所以如何判重边？ ::::

::::success[Solution] 最简单的想法是拿一个 map 存一下这条边是不是被加了，但是常数太大加之带 \log T 飞了。

于是改用 gp_hash_table，这是一个 pb_ds 库里的东西，在 CCF 系列竞赛中可以使用。在日常调试中，需要：

#include<bits/extc++.h>
using namespace __gnu_pbds;

::::

::::success[AC Code]

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define fastio ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define ls (now<<1)
#define rs ((now<<1)|1)
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
const int N=1000005;
const int mod=1;
const int intinf=0x3f3f3f3f;
const ll llinf=0x3f3f3f3f3f3f3f3f;
struct node{
    ll w;
    int u,v;
    friend bool operator <(node _,node __){
        return _.w>__.w;
    }
};
node make_node(int u,int v,ll w){
    node rrat;
    rrat.u=u;
    rrat.v=v;
    rrat.w=w;
    return rrat;
}
gp_hash_table<int,int>mp[N];
std::priority_queue<node>q;
struct Node{
    int a,id;
    friend bool operator <(Node _,Node __){
        return _.a<__.a;
    }
}A[N];
ll a[N];int id[N];
int n,m;
ll sum=0;
vector<pair<int,int> >ans;
void add(int u,int v){
    if(mp[u][v]||u==v)return;
    ans.push_back(make_pair(u,v));
    mp[u][v]=1;mp[v][u]=1;
    sum+=a[u]*a[v];
} 
signed main(){
    fastio;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>A[i].a;A[i].id=i;
    }
    sort(A+1,A+n+1);
    for(int i=1;i<=n;i++){
        a[i]=A[i].a;
        id[i]=A[i].id;
    } 
    for(int i=1;i<=n;i++){
        if(a[i]<0){
            add(i,n);
            q.push(make_node(i,n,a[i]*a[n]));
        }
        else {
            add(i,1);
            q.push(make_node(i,1,a[i]*a[1]));
        }
    }
    int cnt=n-1;
    while(!q.empty()&&cnt<m){
        node tmp=q.top();q.pop();
        int u=tmp.u,v=tmp.v;
        if(a[u]>=0){
            if(v!=n)q.push(make_node(u,v+1,a[u]*a[v+1]));
        }
        else{
            if(v!=1){
                q.push(make_node(u,v-1,a[u]*a[v-1]));
            }
        }
        if(mp[u][v])continue;
        if(u==v)continue;
        cnt++;
        add(u,v);
    }
    cout<<sum<<'\n';
    for(auto p:ans){
        cout<<id[p.fi]<<' '<<id[p.se]<<'\n';
    } 
    return 0;
}

::::