题解：P14023 [ICPC 2024 Nanjing R] 社交媒体

· · 题解

我们把所有数对 (x,y) 分成三类：

  1. 初始时 x,y 都是我的好友，直接记入答案。
  2. 初始时只有 x 是我的好友，此时给 cnt_y 加 1。cnt_y 的含义是只要选择 y 就会给答案加上 cnt_y。
  3. 初始时 x,y 都不是我的好友，这里需要计算一个额外的贡献，对于这样的关系计数，mp_{x,y} \gets mp_{x,y}+1。

处理后面两类增加的贡献。考虑枚举新增的第一位好友 x，对于与 x 不存在第 3 类关系的点 z，没有额外的贡献，直接选择 z 中 cnt_z 最大的那个。

对于与 x 存在第 3 类关系的点 y，暴力枚举这样的 y 计算贡献。增加的贡献是 cnt_x+cnt_y+mp_{x,y}。

由于第 3 类关系只有 O(m) 个，时间复杂度 O(k \log k+m)，瓶颈在于排序。

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
int T,n,m,k;
bool cmp(int a,int b){return a>b;}
unordered_map<int,int> cnt,bj,mp[N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n>>m>>k;
        cnt.clear();bj.clear();
        for(int i=0;i<=k;i++)mp[i].clear();
        for(int i=1;i<=n;i++){
            int f;
            cin>>f;
            bj[f]=1;
        }
        int ans=0;
        for(int i=1;i<=m;i++){
            int a,b;
            cin>>a>>b;
            if(bj[a]&&bj[b])ans++;
            else if(bj[a])cnt[b]++;
            else if(bj[b])cnt[a]++;
            else if(a==b)cnt[a]++;
            else{
                mp[a][b]++;
                mp[b][a]++;
            }
        }
        vector<int> v;
        for(int i=1;i<=k;i++)
            if(cnt[i]!=0)v.push_back(cnt[i]);
        sort(v.begin(),v.end(),cmp);
        int res=0;
        for(int i=1;i<=k;i++){//新增的第一位好友
            if(bj[i])continue;
            if(!v.empty()){
                if(cnt[i]==v[0]){
                    if(v.size()>=2)res=max(res,cnt[i]+v[1]);
                    else res=max(res,cnt[i]);
                }
                else res=max(res,cnt[i]+v[0]);

            }
            for(auto it=mp[i].begin();it!=mp[i].end();it++){
                res=max(res,cnt[i]+cnt[(*it).first]+(*it).second);
            }
        }
        cout<<ans+res<<'\n';
    }
    return 0;
}