题目：https://pintia.cn/problem-sets/994805342720868352/problems/994805456881434624
参考：算法笔记（胡凡）10.3.1
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
const int N=2*1e3+10;
int n,k,num=0,total=0;
int weight[N]={0},ishead[N],gar[N][N]={0};
bool vis[N]={0};
map<string,int> ma;
map<int,string> mb;
map<int,int> hea;
int stringtoint(string s)
{
if (ma.find(s)==ma.end())
{
ma[s]=num;
mb[num++]=s;
return num-1;
}
else
{
return ma[s];
}
}
void findmodal(int now,int& head,int& people,int& totwei)
{
vis[now]=1;
people++;
if (weight[now]>weight[head])
{
head=now;
}
for (int i=0;i<num;i++)
{
if (gar[now][i]>0)
{
totwei+=gar[now][i];
gar[i][now]=gar[now][i]=0;
if (!vis[i])
{
findmodal(i,head,people,totwei);
}
}
}
}
int main()
{
// freopen("in.txt","r",stdin);
cin>>n>>k;
string sa,sb;
int wei;
for (int i=0;i<n;i++)
{
cin>>sa>>sb>>wei;
int ida=stringtoint(sa);
int idb=stringtoint(sb);
weight[ida]+=wei;
weight[idb]+=wei;
gar[ida][idb]+=wei;//这里要用+=，不能单单=!
gar[idb][ida]+=wei;
}
for (int i=0;i<num;i++)
{
if (vis[i]==0)
{
int people=0,head=i,totwei=0;
findmodal(i,head,people,totwei);
if (people>2&&totwei>k)
{
total++;
ishead[head]=people;
}
}
}
cout<<total<<endl;
map<string,int>::iterator it;
for (it=ma.begin();it!=ma.end();it++)
{
if (ishead[it->second]>0)
{
cout<<it->first<<" "<<ishead[it->second]<<endl;
}
} return 0;
}