前置知识: 并查集
作用:求出每个点的祖先编号
各种操作:
1.find操作(找到祖先节点) 时间复杂度:最好$O(1)$,最坏$O(log(n))$
int find(int x){
if(x!=p[x]) p[x]=find(p[x]); //路经压缩,让每个数都指向自己的祖先
return p[x]; //找到祖先节点,返回
}
2.merge操作(合并两个集合)
void merge(int a,int b){
p[find(a)]=find(b); //让他们的祖先节点进行合并
}
C++ 代码
#include<unordered_map>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int N=1010,M=2010;
int n,k,p[M];
struct IFM{
string name1;
string name2;
int talk_time;
}a[N];
bool cmp(IFM t1,IFM t2){
if(t1.name1!=t2.name1) return t1.name1<t2.name1;
else if(t1.name2!=t2.name2) return t1.name2<t2.name2;
else return t1.talk_time<t2.talk_time;
}
int find(int x){
if(x!=p[x]) p[x]=find(p[x]);
return p[x];
}
int main(){
cin>>n>>k;
unordered_map<string,int>mp; //mp将所有字符串映射为1~c的数字
for(int i=1;i<=2*n;i++) p[i]=i;
int c=0;
for(int i=0;i<n;i++){
cin>>a[i].name1>>a[i].name2>>a[i].talk_time;
if(a[i].name1>a[i].name2) swap(a[i].name1,a[i].name2);
}
sort(a,a+n,cmp);
for(int i=0;i<n;i++){
if(!mp.count(a[i].name1)) mp[a[i].name1]=++c;
if(!mp.count(a[i].name2)) mp[a[i].name2]=++c;
int x=mp[a[i].name1],y=mp[a[i].name2];
p[find(x)]=find(y);
}
//将每个人放到对应的团队中
vector<vector<IFM>>team(c+1);
for(int i=0;i<n;i++){
team[find(mp[a[i].name1])].push_back(a[i]); //这里一定要是find!!!,因为每次合并只会改变根节点的祖先,其他都不会改变,所以要用find,
team[find(mp[a[i].name2])].push_back(a[i]);
}
unordered_map<string,int>final_time; //求出每个人最终的总通话时间
unordered_map<int,int>cnt; //记录每个团队有几个人
for(int i=1;i<=c;i++){
unordered_map<string,bool>st;
for(auto t:team[i]){
if(!st[t.name1]){
cnt[i]++;
st[t.name1]=true;
}
if(!st[t.name2]){
cnt[i]++;
st[t.name2]=true;
}
final_time[t.name1]+=t.talk_time;
final_time[t.name2]+=t.talk_time;
}
}
vector<pair<string,int>>all_bosses; //记录每一个团伙的老大
for(int i=1;i<=c;i++){
int all_time=0;
unordered_map<string,bool>st;
for(auto t:team[i]){
if(!st[t.name1]) all_time+=final_time[t.name1];
if(!st[t.name2]) all_time+=final_time[t.name2];
st[t.name1]=st[t.name2]=true;
}
if(all_time/4>k&&cnt[i]>=3){
string boss=team[i][0].name1;
for(auto t:team[i]){
if(final_time[boss]<final_time[t.name1]) boss=t.name1;
else if(final_time[boss]==final_time[t.name1]&&boss>t.name1) boss=t.name1;
if(final_time[boss]<final_time[t.name2]) boss=t.name2;
else if(final_time[boss]==final_time[t.name2]&&boss>t.name2) boss=t.name2;
}
all_bosses.push_back({boss,cnt[i]});
}
}
sort(all_bosses.begin(),all_bosses.end());
cout<<all_bosses.size()<<endl;
for(auto t:all_bosses) cout<<t.first<<" "<<t.second<<endl;
return 0;
}