链接：https://pintia.cn/problem-sets/994805342720868352/problems/994805456881434624 题目思路：这题其实分两步来做：1.将字符串如“aaa”等转化化数字并初始化图；2.用dfs遍历整个图求出；连通块个数，并将连通块中最大权重设为头目然后若连通块满足题设则加入至head数据结构，最后将排序后结果输出（其实可以直接用map，map还是有序的）。注意一个坑点这里图边值的初始化是+a，因为可能完全一样的两个人再通一次话； 代码：
# include<map> # include<stdio.h> # include<string> # include<algorithm> # include<iostream> using namespace std; const int maxn=2020; const int inf=99999999; using namespace std; struct gang{ string head; int num; }ga[1001]; map<string,int>mp1; map<int,string>mp2; int g[maxn][maxn]={0},weight[maxn]={0},s=0; bool vis[maxn]={false}; void dfs(int v,int &head,int &total,int &member){ vis[v]=true; member++; if(weight[v]>weight[head])head=v; for(int i=0;i<mp1.size();i++){ if(g[v][i]>0){ total+=g[v][i]; g[v][i]=g[i][v]=0; if(vis[i]==false)dfs(i,head,total,member); } } return; } void solve(int verge){ int head,total,member; for(int i=0;i<mp1.size();i++){ if(vis[i]==false){ head=i; total=0; member=0; dfs(i,head,total,member); if(member>2&&total>verge){ ga[s].head=mp2[head]; ga[s++].num=member; } } } return; } bool cmp(gang a,gang b){ return a.head<b.head; } int main(){ int n,verge,k=0,total=0; cin>>n>>verge; for(int i=0;i<n;i++){ string a,b; int c; cin>>a>>b>>c; if(mp1.find(a)==mp1.end()){ mp1[a]=k; mp2[k]=a; k++; } if(mp1.find(b)==mp1.end()){ mp1[b]=k; mp2[k]=b; k++; } weight[mp1[a]]+=c; weight[mp1[b]]+=c; g[mp1[a]][mp1[b]]+=c; g[mp1[b]][mp1[a]]+=c; } solve(verge); sort(ga,ga+s,cmp); if(s>0){ printf("%d\n",s); for(int i=0;i<s;i++) cout<<ga[i].head<<" "<<ga[i].num<<"\n"; } else printf("0"); }