把每个用户映射成数字,A~Z
对应数字1~26
第一位乘上27*27
,第二位乘上27
,第三位乘1
,最大数是27*27*26+27*26+26=19682
,开个20000的数组
#include <iostream>
#include <unordered_set>
#include <map>
using namespace std;
const int N = 20010, M = 1010;
int n, k;
int w[N], p[N], sz[N];
int find(int x){
if( p[x]!=x ) p[x]=find(p[x]);
return p[x];
}
void merge(int a, int b){
a = find(a), b = find(b);
if( a!=b ){
p[a] = b; //把a挂到b上
sz[b] += sz[a]; //把a所在集合的大小添加到b
}
}
int s2num(string s){
return (s[0]-'A'+1)*729 + (s[1]-'A'+1)*27 + s[2]-'A'+1;
}
void printS(int x){
printf("%c%c%c", x/729+'A'-1, x%729/27+'A'-1, x%27+'A'-1);
}
int main(){
for( int i=1; i<N; i++ ) p[i]=i, sz[i]=1; //初始化
scanf("%d %d", &n, &k);
string a, b;
int c;
unordered_set<int> st;
for( int i=0; i<n; i++ ){
cin >> a >> b >> c;
int na=s2num(a), nb=s2num(b); //求用户映射的数字
w[na]+=c, w[nb]+=c; //增加用户权重
st.insert(na), st.insert(nb); //记录用户数量
merge(na, nb); //并查集合并
}
map<int, int> res;
for( auto i: st ){
int t = find(i);
if( sz[t]<=2 || res.count(t) ) continue; //集合人数不超过两人或已添加的跳过
int maxW=0, idx=-1, sum=0; //最大权值 最大权值的用户 总权重
for( auto j: st ){
if( find(j)==t ){
sum += w[j];
if( maxW<w[j] ) idx=j, maxW=w[j];
}
}
if( sum/2>k ) res[idx] = sz[t]; //每个用户权重都加了两次,要除以2
}
printf("%d\n", res.size());
for( auto& it: res ){
printS(it.first);
printf(" %d\n", it.second);
}
return 0;
}