本题解起来比较复杂 思路如下： 首先明确最后输出的是两个相关数据，考虑用strcut定义该结果节点，并用vector存储相关数据 输入有字符串，本题是图相关问题，所以考虑用map来解决 先把相关节点转换为整型，利用整型变量分别记录边长和节点本身的通话时长； 利用DFS依次遍历，遍历的过程需注意和树的区别，不是同时取得条件，而是先考虑是否有边，再考虑是否有点（即是否能参与下一次遍历）；
#include<cstdio> #include<iostream> #include<algorithm> #include<map> #include<string> #include<vector> using namespace std; const int maxn=2010; map<string,int> strToint; map<int,string> intTostr; int G[maxn][maxn]={0},weight[maxn]={0}; bool vis[maxn]={false}; int personnum=0; struct node { string head; int nummember; }; vector<node> Gang; int change(string a) { if(strToint.find(a)!=strToint.end()) return strToint[a]; strToint[a]=personnum; intTostr[personnum]=a; return personnum++; } void DFS(int nowVisit,int &head,int &nummember,int &totalvalue) { vis[nowVisit]=true; nummember++; if(weight[nowVisit]>weight[head]) head=nowVisit; for(int i=0;i<personnum;i++) { if(G[nowVisit][i]!=0) { totalvalue+=G[nowVisit][i]; G[nowVisit][i]=G[i][nowVisit]=0; if(vis[i]==false) DFS(i,head,nummember,totalvalue); } } } bool cmp(node a,node b) { return a.head<b.head; } int main() { int n,k,w; string str1,str2; cin>>n>>k; for(int i=0;i<n;i++) { cin>>str1>>str2>>w; int id1=change(str1); int id2=change(str2); weight[id1]+=w; weight[id2]+=w; G[id1][id2]+=w; G[id2][id1]+=w; } for(int i=0;i<personnum;i++) { if(vis[i]==false) { int head=i,nummember=0,totalvalue=0; DFS(i,head,nummember,totalvalue); if(nummember>2&&totalvalue>k) { node temp; temp.head=intTostr[head]; temp.nummember=nummember; Gang.push_back(temp); } } } printf("%d\n",Gang.size()); sort(Gang.begin(),Gang.end(),cmp); for(int i=0;i<Gang.size();i++) { cout<<Gang[i].head<<" "<<Gang[i].nummember<<endl; } }