题目：http://pat.zju.edu.cn/contests/pat-a-practise/1034
题解：
代码：
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<algorithm>
using namespace std;
#define INF 0x6fffffff
map<string,int> weight;
map<string,bool> flag;
map<string,int> out;
map<string,vector<string> > link;
int idx,allWeight;
string st;
void dfs(string x)
{
flag[x]=true;
allWeight+=weight[x];
if(weight[x]>weight[st])//如果当前的权重大于头，则替换头
st=x;
for(vector<string>::iterator it=link[x].begin();it!=link[x].end();++it)
{//遍历相连的结点
if(flag[*it]==false)//判断是否访问过
dfs(*it);
}
++idx;
}
int main()
{
int n,k;
int w;
char a[5],b[5];
string aName,bName;
scanf("%d%d",&n,&k);
for(int i=0;i<n;++i)
{//读入数据
scanf("%s%s%d",a,b,&w);
aName=string(a);
bName=string(b);
if(weight.find(aName)==weight.end())
weight.insert(make_pair(aName,w));
else
weight.find(aName)->second+=w;
if(weight.find(bName)==weight.end())
weight.insert(make_pair(bName,w));
else
weight.find(bName)->second+=w;
link[aName].push_back(bName);
link[bName].push_back(aName);
flag[aName]=false;
flag[bName]=false;
}
for(map<string,bool>::iterator it=flag.begin();it!=flag.end();++it)
{
if(it->second==false)
{
idx=0;
allWeight=0;
st=it->first;
dfs(st);
if(idx>2&&allWeight/2>k)
out[st]=idx;
}
}
printf("%d\n",out.size());
for(map<string,int>::iterator it=out.begin();it!=out.end();++it)
printf("%s %d\n",it->first.c_str(),it->second);
return 0;
}