给出n和k
接下来n行，每行给出a,b,c，表示a和b之间的关系度，表明他们属于同一个帮派
一个帮派由>2个人组成，且总关系度必须大于k。
帮派的头目为帮派里关系度最高的人。
（注意，这里关系度是看帮派里边的和，而不是帮派里所有个人的总和。
如果是按个人算的话，相当于一条边加了两次，所以应该是>2*k）
问你有多少个合格帮派，以及每个帮派里最大的头目是谁，按字典序输出
先并查集一下，然后统计每个帮的成员数、总关系度、以及头目
#include <iostream> #include <cstdio> #include <algorithm> #include <string.h> #include <cmath> #include <map> using namespace std; const int maxn=(1000+5)*2; map<string,int> maps; string id_name[maxn]; int rel[maxn]; //每个人的weight int vis[maxn]; struct Gang{ string name; int num; int tot=0; int maxweight=0; bool operator<(const Gang tmp)const{ if(name.compare(tmp.name)<=0) return true; else return false; } }gang[maxn]; //并查集 struct UF{ int fa[maxn]; int num[maxn]; void init(){ for(int i=0;i<maxn;i++){ fa[i]=i; num[i]=1; } } int find_root(int u){ if(fa[u]!=u) fa[u]=find_root(fa[u]); return fa[u]; } void Union(int x,int y){ int fx=find_root(x); int fy=find_root(y); if(fx!=fy){ fa[fy]=fx; num[fx]+=num[fy]; } } }uf; int main() { char str1[20],str2[20]; int a; int cnt=0; int n,k; uf.init(); memset(rel,0,sizeof(rel)); scanf("%d %d",&n,&k); for(int i=0;i<n;i++){ cin>>str1>>str2; scanf("%d",&a); if(maps[str1]==0){ maps[str1]=++cnt; id_name[cnt]=str1; } if(maps[str2]==0){ maps[str2]=++cnt; id_name[cnt]=str2; } rel[maps[str1]]+=a; rel[maps[str2]]+=a; uf.Union(maps[str1],maps[str2]); } memset(vis,0,sizeof(vis)); int gangcnt=0; //父亲一样的属于同一个组，建立父亲id与帮派之间的映射 for(int i=1;i<=cnt;i++){ int group=uf.find_root(i); if(!vis[group]){ vis[group]=++gangcnt; gang[gangcnt].num=uf.num[group]; gang[gangcnt].tot+=rel[i]; gang[gangcnt].maxweight=rel[i]; gang[gangcnt].name=id_name[i]; } else{ int id=vis[group]; gang[id].tot+=rel[i]; if(rel[i]>gang[id].maxweight){ gang[id].name=id_name[i]; gang[id].maxweight=rel[i]; } } } sort(gang+1,gang+gangcnt+1); int ans=0; for(int i=1;i<=gangcnt;i++){ //tot要除以2，因为一条边的weight加了2次 if(gang[i].num>2&&gang[i].tot/2>k){ ans++; } } printf("%d ",ans); for(int i=1;i<=gangcnt;i++){ if(gang[i].num>2&&gang[i].tot/2>k){ cout<<gang[i].name<<" "<<gang[i].num<<endl; } } return 0; }