AcWing 1518. 团伙头目(并查集)
原题链接
中等
作者:
不会写的带阿米
,
2023-11-21 20:50:10
,
所有人可见
,
阅读 53
自用 放在主页复习
#include<iostream>
#include<unordered_map>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1010;
int p[2*N];//双向边,开两倍
int n,m;
unordered_map<int,int> total;//团队的总权重
unordered_map<int,int> power;//团队的总权重
unordered_map<int,int> nums;//团队的人数
unordered_map<string,vector<string>> g;//a和b有关联
unordered_map<string,int> index;//名字到id的映射
unordered_map<int,string> r;//id到名字的映射
int st[2*N];//如果是出现过的人,记录一下
int idx;
vector<pair<string,int>> res;//答案数组
int find(int k){
if(p[k]==k)return k;
else return p[k]=find(p[k]);
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){
string a,b;
int time;
cin>>a>>b>>time;
if(!index.count(a))index[a]=++idx;//第一次出现,创建一个id
if(!index.count(b))index[b]=++idx;
int xa=index[a],xb=index[b];//根据名字找id
r[xa]=a;//根据id找名字
r[xb]=b;
total[xa]+=time;//某个人的通话总时间
total[xb]+=time;
nums[xa]=1;//一开始只有自己一个人
nums[xb]=1;
g[a].push_back(b);//连边
g[b].push_back(a);
st[xa]=true;//出现过的人
st[xb]=true;
power[xa]+=time;//其实和total存一样的内容,只不过total在读完n后是固定不变的,power在集合合并的时候会转移到老大身上
power[xb]+=time;
}
for(int i=0;i<N;i++)p[i]=i;
for(auto i:g){
string x=i.first;auto t=i.second;
for(auto j:t){//跟i相连的所有边
string y=j;
int xa=index[x],xb=index[y];
xa=find(xa),xb=find(xb);
if(xa!=xb){//不在一个集合
if(total[xa]<total[xb])swap(xa,xb);//因为题目要输出总通话最长的老大
nums[xa]+=nums[xb];
power[xa]+=power[xb];
p[xb]=xa;
}
}
}
for(int i=0;i<N;i++){
if(st[i]&&p[i]==i&&nums[i]>2&&power[i]/2>m){//power的总权重存了两边,这里/2
string name=r[i];
res.push_back({name,nums[i]});
}
}
sort(res.begin(),res.end());
cout<<res.size()<<endl;
for(auto i:res){
cout<<i.first<<" "<<i.second<<endl;
}
return 0;
}