专栏文章

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

wwyc0607
P14023题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miny1ysa
此快照首次捕获于
2025/12/02 10:13
3 个月前
此快照最后确认于
2025/12/02 10:13
3 个月前
查看原文

思路：

记录一个 ansans 为已经有的评论数，resres 为通过选择加好友而获得的评论数的最大值。
开一个 mapmap，其中 map[a,b]map[a,b] 表示 a 在 b 评论了多少。
gx[i]gx[i] 表示在只选 i 时多的评论个数。
对于每个评论 x,yx,y：
  • 如果都是朋友，ansans 加一。
  • 如果只有一个是朋友，那么那个不是朋友的 gx 加一。
  • 如果都不是，mp[x,y]mp[x,y] 加一。
定义 mxmx 数组为选 i 时的最大评论（包括了选第二个）。 预处理 mxmx 数组，对于每个 mp[x,y]mp[x,y] 不等于 0,更新 mx[x]mx[x] 和 mx[y]mx[y] 即可。
resres 为 mxmx 数组的最大值，resres 和 gxgx 数组的最大和次大值之和之间的最大值。
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';
	}
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...