题解：P14023 [ICPC 2024 Nanjing R] 社交媒体
wyc0607
·
·
题解
思路：
记录一个 ans 为已经有的评论数，res 为通过选择加好友而获得的评论数的最大值。
开一个 map，其中 map[a,b] 表示 a 在 b 评论了多少。
对于每个评论 $x,y$：
- 如果都是朋友，$ans$ 加一。
- 如果只有一个是朋友，那么那个不是朋友的 gx 加一。
- 如果都不是，$mp[x,y]$ 加一。
定义 $mx$ 数组为选 i 时的最大评论（包括了选第二个）。
预处理 $mx$ 数组，对于每个 $mp[x,y]$ 不等于 0,更新 $mx[x]$ 和 $mx[y]$ 即可。
$res$ 为 $mx$ 数组的最大值，$res$ 和 $gx$ 数组的最大和次大值之和之间的最大值。
```cpp
#include<bits/stdc++.h>
using namespace std;
bool f[200005];
int gx[200005];
int mx[200005];
map<pair<int,int>,int> mp;
main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
cin>>T;
while(T--){
int n,m,k;
cin>>n>>m>>k;
for(int i=1;i<=k;i++) f[i]=gx[i]=mx[i]=0;
mp.clear();
for(int i=1;i<=n;i++){
int x;
cin>>x;
f[x]=1;
}
int ans=0;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
if(f[x]==f[y]&&f[x]==1) ans++;
else{
if(x==y){
gx[x]++;
continue;
}
if(x>y) swap(x,y);
if(f[x]==1) gx[y]++;
else if(f[y]==1) gx[x]++;
else mp[{x,y}]++;
}
}
if(k-n<=1){
cout<<m<<'\n';
continue;
}
for(auto &[x,y]:mp){
pair<int,int> pr=x;
int a=pr.first,b=pr.second;
mx[a]=max(mx[a],gx[a]+gx[b]+y);
mx[b]=max(mx[b],gx[a]+gx[b]+y);
}
vector<int> v;
int res=0;
for(int i=1;i<=k;i++){
res=max(res,mx[i]);
if(!f[i]) v.push_back(gx[i]);
}
sort(v.begin(),v.end());
if(v.size()==1) res=max(res,v[0]);
res=max(res,v[v.size()-1]+v[v.size()-2]);
//不需要考虑他们之间的评论，因为这样一定会在 mx 数组中计算过。
cout<<ans+res<<'\n';
}
}
```