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

koukou · 2026-05-17 20:58:04 · 题解

考虑将每条评论按照 "还需要哪些人成为好友" 来分类。

设初始好友集合为 F，|F| = n。对于一条评论 (a, b)：

• 若 a, b \in F，则这条评论已经可见，计入答案 ans。
• 若恰好一个在 F 中，另一个不在（不妨设 a \in F, b \notin F），则只需选 b 为好友即可看到。令 c_1[b] 加一，其中 c_1[x] 表示只选 x 一人就能新增看到的评论数。
• 若 a = b 且 a \notin F，则只需选 a 为好友即可看到。令 c_1[a] 加一。
• 若 a, b \notin F 且 a \neq b，则必须同时选 a 和 b 为好友才能看到。令 c_2[\{\min(a,b), \max(a,b)\}] 加一，其中 c_2[\{x, y\}] 表示必须同时选 x 和 y 两人才能看到的评论数。

这样，对于任意非好友用户 i，c_1[i] 表示只选 i 一人就能新增看到的评论数。对于任意两个不同的非好友用户 i, j，c_2[\{i, j\}] 表示必须同时选这两人才能看到的评论数。

考虑选择策略。设新选的好友集合为 S \subseteq U \set \min us F，|S| \le 2。

若 |S| = 1，设 S = \{i\}，则新增可见评论数为 c_1[i]。因为 c_1[i] 中的每条评论都仅依赖 i 一人，且这些评论互不重叠。

若 |S| = 2，设 S = \{i, j\}，则新增可见评论数为 c_1[i] + c_1[j] + c_2[\{i, j\}]。这是因为三类评论互不相交：

不存在一条评论同时属于两类，因为每条评论所需的新好友集合是唯一确定的。

因此，问题转化为求 \max(0, \max_i c_1[i], \max_{i < j} (c_1[i] + c_1[j] + c_2[\{i, j\}]))。

对于选两人的最大收益，需要分两种情况考虑：

情况一：两人之间有共同评论（c_2[\{i, j\}] > 0）。直接遍历 c_2 中的所有对即可，因为每对至少对应一条评论，总对数不超过 m。

情况二：两人之间没有共同评论（c_2[\{i, j\}] = 0）。此时收益退化为 c_1[i] + c_1[j]，只需选取 c_1 最大的两个非好友用户。维护非好友中 c_1 的最大值和次大值即可。

最后，答案即为 ans + \max(0, \max_i c_1[i], \max_{i < j} (c_1[i] + c_1[j] + c_2[\{i, j\}]))。

这样分类相当于穷举了所有情况，所以肯定是正确的。

:::success[代码]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
bool vis[N];
int T, n, m, k, c1[N];
map<pair<int, int>, int> c2;
void solve()
{
    cin >> n >> m >> k;
    c2.clear();
    for(int i = 1; i <= k; i++) c1[i] = vis[i] = 0;
    for(int i = 1; i <= n; i++)
    {
        int x; 
        cin >> x;
        vis[x] = 1;
    }    
    int ans = 0;
    vector<pair<int,int>> edges;
    for(int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        edges.push_back({u, v});        
        if(vis[u] == 1 && vis[v] == 1) ans++;
        else if(vis[u] == 1 && vis[v] == 0) c1[v]++;
        else if(vis[u] == 0 && vis[v] == 1) c1[u]++;
        else if(u == v) c1[u]++;
    }
    for(auto &e : edges)
    {
        int u = e.first, v = e.second;
        if(vis[u] == 0 && vis[v] == 0 && u != v)
        {
            if(u > v) swap(u, v);
            c2[{u, v}]++;
        }
    }
    int max1 = 0;
    for(int i = 1; i <= k; i++)
    {
        if(vis[i] == 0) max1 = max(max1, c1[i]);
    }
    int max2 = 0;
    for(auto &it : c2)
    {
        int u = it.first.first, v = it.first.second;
        max2 = max(max2, c1[u] + c1[v] + it.second);
    }
    int mx1 = 0, mx2 = 0;
    for(int i = 1; i <= k; i++)
    {
        if(vis[i] == 0)
        {
            if(c1[i] > mx1) mx2 = mx1, mx1 = c1[i];
            else if(c1[i] > mx2) mx2 = c1[i];
        }
    }
    max2 = max(max2, mx1 + mx2);
    cout << ans + max({0, max1, max2}) << "\n";
    return;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen(".in", "r", stdin);
//    freopen(".out", "w", stdout);
    cin >> T;
    while(T--) solve();
    return 0;
}

:::