P9562 [SDCPC2023] G-Matching 题解

题目描述

给定长度为 \(n\) 的整数序列 \(a_1, a_2, \cdots, a_n\)，我们将从该序列中构造出一张无向图 \(G\)。具体来说，对于所有 \(1 \le i < j \le n\)，若 \(i - j = a_i - a_j\)，则 \(G\) 中将存在一条连接节点 \(i\) 与 \(j\) 的无向边，其边权为 \((a_i + a_j)\)。

求 \(G\) 的一个匹配，使得该匹配中所有边的边权之和最大，并输出最大边权之和。

请回忆：无向图的匹配，指的是从该无向图中选出一些边，使得任意两条边都没有公共的节点。特别地，不选任何边也是一个匹配。

思路

首先我们看到题目中的一句话：

若 \(i - j = a_i - a_j\)，则 \(G\) 中将存在一条连接节点 \(i\) 与 \(j\) 的无向边

我们把这个式子两边同时加上 \(j\)，减去 \(a_i\)，可以得到如下的式子：

因此我们可以把原数组转换一下，第 \(i\) 项 \(a_i\) 变成 \(i - a_i\)，所有处理后值相同的点之间都会有一条边，形成一个完全图，我们可以把这些点全部塞进一个 map 中。

map<int,vector<int> >Edge;

for(int i=1;i<=n;i++){
    scanf("%lld",&a[i]);
    Edge[a[i]-i].push_back(a[i]);
}

然后开始分别处理每一个完全子图。由于要我们求无向图的匹配，一个点不会被选超过两次，所以我们可以把所有点按照点权从大到小排序，每一次选择一对点，判断这两个点的和是否为正数，如果是，那么就一定选，否则直接 break 即可。

for(auto it:Edge){
    vector<int>E=it.second;
    sort(begin(E),end(E),[](int a,int b){return a>b;});
    int a=0x3f3f3f3f,b=0x3f3f3f3f;
    for(auto it:E){
        if(a==0x3f3f3f3f){
            a=it;
        }else{
            b=it;
            if(a+b>0) ans+=a+b,a=b=0x3f3f3f3f;
            else      break;
        }
    }
}

完整 Code

#include <bits/stdc++.h>
#define int long long
using namespace std;

map<int,vector<int> >Edge;
int T,n,a[500005],ans;

signed main()
{
    scanf("%lld",&T);
    while(T--){
        Edge.clear();ans=0;
        scanf("%lld",&n);
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
            Edge[a[i]-i].push_back(a[i]);
        }
        for(auto it:Edge){
            vector<int>E=it.second;
            sort(begin(E),end(E),[](int a,int b){return a>b;});
            int a=0x3f3f3f3f,b=0x3f3f3f3f;
            for(auto it:E){
                if(a==0x3f3f3f3f){
                    a=it;
                }else{
                    b=it;
                    if(a+b>0) ans+=a+b,a=b=0x3f3f3f3f;
                    else      break;
                }
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}