并查集

还有2个测试点没过
22分
求指点

#include<bits/stdc++.h>
using namespace std;
const int  maxn = 3005;
int f[maxn],val[maxn];
map<int, string> IS;
map<string, int> SI;
int person=1;
struct node{
	int a,cnt,total,tag,mm;
}E[maxn];
void init(){
	for(int i=0;i<maxn;i++){
		f[i] = i;
		E[i].a=E[i].cnt=E[i].total=E[i].mm=0;
		val[i] = 0;
	}
}
int find(int x){
	if(x == f[x]) return x;
	return f[x] = find(f[x]);
}
bool cmp(node a, node b){
	if(a.tag != b.tag) return a.tag > b.tag;
	else return a.a < b.a;
}
int change(string str){ 
	if(SI.find(str) != SI.end()) return SI[str];
	else{
		SI[str] = person;
		IS[person] = str;
		return person++;
	}
}
int main(){
	int n,m,x,a,b;
	string str1,str2;
	init();
	cin>>n>>m;
	for(int i=0;i<n;i++){
		cin>>str1>>str2>>x;
		a = change(str1);
		b = change(str2);
		int fa = find(a);
		int fb = find(b);
		val[a] += x;  
		val[b] += x;
		if(fa != fb) f[fa] = fb;
			
	}

	for(int i=0;i<maxn;i++){ //筛选 
		int d = find(i);  
		if(val[i]!=0){ 
			if(E[d].mm < val[i]){
				E[d].mm = val[i];
				E[d].a = i;
			} 
			E[d].total += val[i];
			E[d].cnt++;
		}
	}
	
	int k=0;
	for(int i=0;i<maxn;i++){
		if(E[i].cnt > 2 && E[i].total/2 > m){
			k++;
			E[i].tag=1;
		}else 
			E[i].tag = 0;
	}
	sort(E,E+maxn,cmp);
	cout<<k<<endl;
	for(int i=0;i<k; i++){
		cout<<IS[E[i].a]<<" "<<E[i].cnt<<endl;
	}
	return 0;
}