//
// main.cpp
// PAT_1034. Head of a Gang
//
// Created by wjq on 17/4/29.
// Copyright © 2017年 wjq. All rights reserved.
//
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
using namespace std;
int N,K,id=0,wei;
string A,B;
map <string,int> m;
map <int,string> mm;
int p[2010]; //用来统计某个老大的权重
int father[2010]; //用来记录某个小弟的老大是谁
int r[2010]; //用来统计某个老大拥有的小弟个数
struct fa
{
int maxW; //用来记录团队中的总权重*2
int sumW; //用来记录团队中权重最大的那个人的权重
string nowfather; //用来记录团队中权重最大的人名
};
map<int,fa> result;
void Init()
{
for(int i=0;i<2010;i++)
{
p[i]=0;
father[i]=i;
r[i]=1;
}
}
int Find(int x)
{
while(x!=father[x])
x=father[x];
return x;
}
void Union(int x,int y)
{
int fx=Find(x),fy=Find(y);
if(fx!=fy)
{
father[fy]=fx;
r[fx]+=r[fy];
}
}
int main(int argc, const char * argv[])
{
Init();
cin>>N>>K;
for(int i=0;i<N;i++)
{
cin>>A>>B>>wei;
if(m.find(A)==m.end()) //如果字符串A未出现过
{
m[A]=id; //给字符串A一个编号
mm[id]=A;
p[id]+=wei; //该编号下的权重增加
id++;
}
else
p[m[A]]+=wei;
if(m.find(B)==m.end())
{
m[B]=id;
mm[id]=B;
p[id]+=wei;
id++;
}
else
p[m[B]]+=wei;
Union(m[A],m[B]);
}
int resu[2010];int k=0;
for(int i=0;i<id;i++)
{
int root=Find(i);
if(result.find(root)==result.end())
{
fa temp;
temp.maxW=p[i];
temp.nowfather=mm[i];
temp.sumW=p[i];
result[root]=temp;
resu[k++]=root;
}
else
{
result[root].sumW+=p[i];
if(p[i]>result[root].maxW)
{
result[root].maxW=p[i];
result[root].nowfather=mm[i];
}
}
}
int ans=0;
pair<string,int> g[2010];int sb=0;
for(int i=0;i<k;i++)
if(r[resu[i]]>2&&result[resu[i]].sumW/2>K)
{
ans++;
g[sb++]=make_pair(result[resu[i]].nowfather, r[resu[i]]);
}
sort(g,g+ans);
cout<<ans<<endl;
for(int i=0;i<ans;i++)
cout<<g[i].first<<" "<<g[i].second<<endl;
return 0;
}
这题用并查集做,stl的合理运用能够加快解题速度.
