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

Void_Trailwalker · 2025-10-22 15:23:20 · 题解

blog

简化题意

给你 k 个点以及 m 条边，其中有 n 个点已经被选择，问至多再选两个点后最多有多少条边的端点都被选了。

思路

我们可以把边分为 3 类：

• 两个端点都被选择了，这时直接加入答案。
• 有一个端点被选择，我们将另一个端点的贡献 +1，特殊的，自环也算这种情况。
• 两个端点都没被选择，则先把这条边存起来。

选择可以分为 2 类：

• 选择的两个点之间没有联系，或只能选一个点：
  我们将所有点的贡献排序，选最大的两个（被选择的点没有贡献；虽然这两个点之间可能会有边，但是不影响最终答案，可以自己想一下为什么）。
• 选择两个之间有边的点，这时候枚举每一条边，答案的变化量为 两个端点的贡献之和 + 这条边的出现次数。
  排序后可以轻松完成。

  code

  pl 就是贡献数组，pl2 是贡献数组的备份，方便计算的时候直接用，不用再排序一次。
  ans 是不选的时候的答案，change 是答案的最大变化量。

  cin >> n >> m >> k;ans = 0 , edge.clear() , cnt = 1;
  for(int i=1;i<=k;i++)pl[i] = pl2[i] = 0 , fl[i] = 0;
  for(int i=1;i<=n;i++){
  int x;cin >> x;
  fl[x] = 1;
  }
  for(int i=1;i<=m;i++){
  int u , v;cin >> u >> v;
  if(fl[u]&&fl[v])ans++;
  else if(fl[u]||u==v)pl[v]++ , pl2[v]++;
  else if(fl[v])pl[u]++ , pl2[u]++;
  else edge.push_back({u,v});
  }
  sort(pl+1,pl+k+1);
  sort(edge.begin(),edge.end());
  int change = pl[k] + pl[k-1]; 
  for(int i=0;i<edge.size();i++){
  if(i&&(edge[i].u!=edge[i-1].u||edge[i].v!=edge[i-1].v))cnt = 1;
  change = max(change,pl2[edge[i].u]+pl2[edge[i].v]+cnt) , cnt++;
  }
  cout << ans + change << "\n";