测试点三没过的话,很可能是因为,如果两个人重复打电话,那么边权要加一起,而不是直接就等于
#include<iostream>
#include<string>
#include<map>
#include<queue>
#include<algorithm>
using namespace std;
map<string,int> StrToInt;
map<int,string> IntToStr;
int picture[2010][2010],weight[2010],index,k,n,cnt;//index用来指导现在的这个string的编号是多少,k是阈值,cnt用来记录最终的个数
bool vis[2010];
int change(string temp){
if(StrToInt.count(temp) == 0) {StrToInt[temp] = index;IntToStr[index] = temp; return index++;}
return StrToInt[temp];
}
/*struct node{
string name;int num;
void change(int a,int b){name = IntToStr[a];num = b;}
}ans[2010];//用来记录每个gang的头目和人数*/
map<string,int> ans;
void BFS(int v){
queue<int> q;
q.push(v);
vis[v] = false;
int sum = 0,membernum = 0;//用来计算总边权,用来记录总人数
int maxname,maxnum = 0;//用来记录权重最大的人
while(q.size()){
int temp = q.front();q.pop();membernum ++;
if(weight[temp] > maxnum){maxname = temp,maxnum = weight[temp];}
for(int i = 0;i <= n;i++){
if(picture[temp][i]){
sum += picture[temp][i];
picture[temp][i] = picture[i][temp] = 0;
if(vis[i]){vis[i] = false;q.push(i);}
}
}
}
if(sum > k && membernum > 2) //ans[cnt++].change(maxname,membernum);
ans[IntToStr[maxname]] = membernum;
}
/*bool cmp(node a,node b){
return a.name <= b.name;
}*/
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
cin>>n>>k;
for(int i = 0;i < n;i++){
string nameA,nameB;int edge_weight;
cin>>nameA>>nameB>>edge_weight;
int code_A = change(nameA),code_B = change(nameB);
weight[code_A] += edge_weight ,weight[code_B] += edge_weight;
picture[code_B][code_A] += edge_weight;
picture[code_A][code_B] += edge_weight;
vis[code_A] = vis[code_B] = true;
}
n *= 2;
for(int i = 0;i <= n;i++)
if(vis[i])
BFS(i);
/*cout<<cnt<<endl;
sort(ans,ans + cnt,cmp);
for(int i = 0;i < cnt;i++)cout<<ans[i].name<<" "<<ans[i].num<<endl;*/
cout<<ans.size()<<endl;
for(map<string,int>::iterator it = ans.begin();it != ans.end();it++)
cout<<it->first<<" "<<it->second<<endl;
}