Head of a Gang (30)

#include <iostream>
#include <set>
#include <vector>
#include <map>
#include <string>

using namespace std;

struct Person
{
    string name; int weight, father;
    Person(){}
    Person(string _name, int _weight, int _father) {
        name = _name; weight = _weight;
        father = _father;
    }
};

struct Group
{
    string head; int numOfPerson;
    int maxWeight, sumWeight;
    Group() {
        numOfPerson = 0; maxWeight = 0;
        sumWeight = 0;
    }
    bool operator<(const Group& that) const{
        return (head < that.head);
    }
};

vector<Person> persons;
// 并查集的两个操作
int getFather(int x)
{
    if(x != persons[x].father) {
        persons[x].father = getFather(persons[x].father);
    }
    return persons[x].father;
}
void unionSet(int x, int y)
{
    x = getFather(x);
    y = getFather(y);
    if(x!=y) {
        persons[x].father = y;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    // 读入数据
    int N, K; cin >> N >> K;
    map<string, int> link; vector<Group> groups;
    string first, second; int weight, idx1, idx2;
    while(N--) {
        cin >> first >> second >> weight;
        // 按照first和second是否已经在分组里分成四个情况
        if(link.count(first) && link.count(second)) {
            idx1 = link[first]; idx2 = link[second];
            persons[idx1].weight += weight;
            persons[idx2].weight += weight;
        } else if(link.count(first) && !link.count(second)) {
            idx1 = link[first]; idx2 = persons.size();
            link[second] = idx2;
            persons.push_back(Person(second,weight,idx2));
            groups.push_back(Group());
            persons[idx1].weight += weight;
        } else if(!link.count(first) && link.count(second)) {
            idx1 = persons.size(); idx2 = link[second];
            link[first] = idx1;
            persons.push_back(Person(first,weight,idx1));
            groups.push_back(Group());
            persons[idx2].weight += weight;
        } else {
            idx1 = persons.size(); link[first] = idx1;
            idx2 = idx1+1; link[second] = idx2;
            persons.push_back(Person(first,weight,idx1));
            persons.push_back(Person(second,weight,idx2));
            groups.push_back(Group()); groups.push_back(Group());
        }
        unionSet(idx1, idx2);
        groups[idx1].sumWeight += weight;
    }

    // 处理数据：分组并得到结果
    int tf; int num = persons.size();
    set<Group> result;
    // 计算各分组的信息
    for(int i=0; i<num; i++) {
        tf = getFather(i);
        groups[tf].numOfPerson++;
        if(tf != i) {
            groups[tf].sumWeight += groups[i].sumWeight;
        }
        if(groups[tf].maxWeight < persons[i].weight) {
            groups[tf].maxWeight = persons[i].weight;
            groups[tf].head = persons[i].name;
        }
    }
    // 找出符合要求的分组
    for(int i=0; i<num; i++) {
        if(groups[i].sumWeight > K && groups[i].numOfPerson > 2) {
            result.insert(groups[i]);
        }
    }

    // 输出结果
    cout << result.size() << endl;
    set<Group>::iterator iter = result.begin();
    for(;iter != result.end(); iter++) {
        cout << (*iter).head << " " << (*iter).numOfPerson << endl;
    }
    return 0;
} 

#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;
const int maxn=2010;
map<string,int> SToN,gang;                       //字符串姓名->编号、保存每个集团的头目和人数
map<int,string> NToS;                            //编号->字符串姓名
vector<int> Adj[maxn];
bool vis[maxn]={false};
int weight[maxn]={0};                            //存储每个结点的权值
int n,limit,vnum=0,tempnum,tempweight,head;      //vnum为图中结点个数
int change(string s){                            //字符串姓名转编号
    if(SToN.count(s)!=0) return SToN[s];         //若之前出现过
    else{
        SToN[s]=vnum;
        NToS[vnum]=s;
        return vnum++;
    }
}
void DFS(int u){
    vis[u]=true;
    tempnum++;
    tempweight+=weight[u];
    if(weight[u]>weight[head]) head=u;           //当前点权值大于头目，更新头目
    for(int i=0;i<Adj[u].size();i++){
        int v=Adj[u][i];
        if(vis[v]==false) DFS(v);
    }
}
void DFSTrave(){
    for(int i=0;i<n;i++){
        if(vis[i]==false){
            head=i;                              //默认该集团(连通分量）头目为根
            tempnum=tempweight=0;                //初始化
            DFS(i);
            if(tempnum>2&&tempweight>2*limit)    //若该集团人数大于2，且结点权值之和（即边权值和的2倍）大于给定量
                gang[NToS[head]]=tempnum;        //将该集团头目与人数加入
        }
    }
}
int main(){
    cin>>n>>limit;
    string s1,s2;
    int w;
    for(int i=0;i<n;i++){
        cin>>s1>>s2>>w;
        int id1=change(s1);                      //转换成编号
        int id2=change(s2);
        Adj[id1].push_back(id2);                 //存储邻接点
        Adj[id2].push_back(id1);
        weight[id1]+=w;                          //更新结点权值
        weight[id2]+=w;
    }
    DFSTrave();
    cout<<gang.size()<<endl;
    for(auto it=gang.begin();it!=gang.end();it++)
        cout<<it->first<<" "<<it->second<<endl;
    return 0;
} 

#include<iostream>
#include<string>
#include<map>
using namespace std;
map<string,int> stringToInt;
map<int,string> intToString;
map<string, int> Gang; // use map to auto sort the key(name)
int number = 0; // record person number
const int maxn  = 1010;
const int INF = 100000000;
int G[maxn][maxn] = {0}, weight[maxn] = {0};
bool vis[maxn] = {false};
int n,k,w;
int getIndex(string name){  if(stringToInt.find(name)!=stringToInt.end()){  return stringToInt[name];  }  else{  stringToInt[name] = number;  intToString[number] = name;  return number++;  }
}

void DFS(int vis_i, int &head , int &numMember, int & toTalValue){  numMember ++ ;  vis[vis_i] = true;  if(weight[vis_i] > weight[head]){  head = vis_i;  }  for(int i=0; i < number; i++){  if(G[vis_i][i] > 0){  toTalValue += G[vis_i][i];  G[vis_i][i] = G[i][vis_i] = 0;  if(!vis[i]){  DFS(i, head, numMember, toTalValue);  }  }  }
}

void DFS_ALL(){  for(int i = 0; i < number ;i++){  if(!vis[i]){  int head = i , numMember = 0 , toTalValue = 0;  DFS(i,head,numMember,toTalValue);  if(numMember > 2 && toTalValue > k){  Gang[intToString[head]] = numMember;  }  }  }
}


int main(){  //freopen("a.txt","r",stdin);    string name1,name2;  cin >> n >> k;  while(n > 0){  cin >> name1 >> name2 >> w;  int i = getIndex(name1);  int j = getIndex(name2);  G[i][j]  += w;  G[j][i]  += w;  weight[i] += w;  weight[j] += w;  n--;  }  DFS_ALL();  cout << Gang.size() << endl;  map<string, int>:: iterator it;  for(it = Gang.begin(); it != Gang.end() ; it++){  cout << it->first << " " << it->second<<endl;  }    return 0;
}

#include<bits/stdc++.h>
using namespace std;

const int Max=2010;

map<int,string> intTostring;
map<string,int> stringToint;
map<string,int> gang;
int n,k,nump;
int w[Max],G[Max][Max];
bool visit[Max];

void DFS(int now,int & head,int & member,int & totalv) {
	member++;
	visit[now]=1;
	if(w[now]>w[head]) {
		head=now;
	}
	for(int i=0; i<nump; i++) {
		if(G[now][i]>0) {
			totalv+=G[now][i];
			G[now][i]=G[i][now]=0;
			if(!visit[i]) {
				DFS(i,head,member,totalv);
			}
		}
	}
}

void DFSTrave() {
	for(int i=0; i<nump; i++) {
		int head=i,member=0,totalv=0;
		if(!visit[i]) {
			DFS(i,head,member,totalv);
		}
		if(member>2&&totalv>k) {
			gang[intTostring[head]]=member;
		}
	}
}

int change(string str) {
	if(stringToint.find(str)!=stringToint.end()) {
		return stringToint[str];
	} else {
		stringToint[str]=nump;
		intTostring[nump]=str;
		return nump++;
	}
}

int main() {
	scanf("%d %d",&n,&k);
	int W;
	string s1,s2;
	for(int i=0; i<n; i++) {
		cin>>s1>>s2>>W;
		int id1=change(s1);
		int id2=change(s2);
		w[id1]+=W;
		w[id2]+=W;
		G[id1][id2]+=W;
		G[id2][id1]+=W;
	}
	DFSTrave();
	printf("%d\n",gang.size());
	for(auto it=gang.begin(); it!=gang.end(); it++) {
		printf("%s %d\n",it->first.c_str(),it->second);
	}
	return 0;
}

本来用的dfs 可是一直有坑 debug 很久才把PAT过了 但牛客这儿过不了
受评论启发用了并查集 很快就解决了 注释写的还算全 凑活看吧

#include
#include
#include
#include
#include
using namespace std;
map fa;//存爸爸
map memberw;//存每个成员的weight
map> gang;//存每个帮派的成员名字
set name;//存有所有人员的名单
int N, K;
struct dataa//存每个合格帮派的老大名 和帮派人数 （不想好好取名字了TAT）
{
    string head;
    int num;
};
vector ans;//存最后输出结果
bool cmp(dataa a, dataa b)//按字典序排列答案
{
    return a.head < b.head;
}
string find(string name)//找成员祖先
{
    if (fa[name] == name)
        return name;
    else
        return find(fa[name]);
}
void unionset(string n1, string n2)//合并成员
{
    n1 = find(n1);
    n2 = find(n2);
    if (n1 == n2)
        return;
    fa[n1] = n2;
}
int main()
{
    cin >> N >> K;
    for (int i = 0; i < N;i++)
    {
        string n1, n2;
        int w;
        cin >> n1 >> n2 >> w;
        memberw[n1] += w;
        memberw[n2] += w;
        if (!fa.count(n1))//假如第一次出现这个成员名 就把祖先初始化为自己
            fa[n1] = n1;
        if (!fa.count(n2))
            fa[n2] = n2;
        unionset(n1, n2);//将两个人合并到一个帮派
        name.insert(n1);
        name.insert(n2);//存人名
    }
    for (auto n : name)//把同一个帮派的人放在一个数组里 head暂时以第一个进帮派的人代替 之后再计算
    {
        string head = find(n);
        gang[head].push_back(n);
    }
    for (auto g:gang)//遍历每一个帮派
    {
        int sum = 0;//算帮派总weight
        int maxw = 0;//最大的weight 用来确定帮派老大
        string head;
        for (auto mem : g.second)
        {
            sum += memberw[mem];//给sum加上所有成员的weight 之后/2就是帮派的weight
            if (maxw < memberw[mem])//找老大
            {
                head = mem;
                maxw = memberw[mem];
            }
        }
        sum /= 2;
        if (sum > K && g.second.size() > 2)//假如符合帮派标准 人数 > 2  sum > K 存到答案数组
        {
            dataa temp;
            temp.head = head;
            temp.num = g.second.size();
            ans.push_back(temp);
        }
    }
    sort(ans.begin(), ans.end(), cmp);//排序
    cout << ans.size() << endl;
    for (auto a : ans)//输出即可
        cout << a.head << ' ' << a.num << endl;
    return 0;
} 

//Head of a Gang (30分)
#include <iostream>
(720)#include <vector>
#include <cstring>
(803)#include <algorithm>

using namespace std;
int n, k, x = 0;
struct call {
    int minter, con = 0;
    string n1, n2;
};
vector<struct call> array;
vector<pair<string, int>> gang[1024];
int weight[1024];

bool comp1(pair<string, int> &a, pair<string, int> &b) {
    return a.second > b.second;
}

bool comp2(pair<string, int> &a, pair<string, int> &b) {
    return a.first < b.first;
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        struct call node;
        cin >> node.n1 >> node.n2 >> node.minter;
        array.push_back(node);
    }
    memset(weight, 0, sizeof(weight));
    int ji = 0;
    while (true) {
        int number = 0, c = 0;
        for (int i = 0; i < array.size(); i++)
            if (array[i].con == 1) c++;
        if (c == array.size()) break;
        for (int i = 0; i < array.size(); i++) {
            if (array[i].con != 0) continue;
            if (ji == 0) {
                gang[x].push_back(pair<string, int>(array[i].n1, array[i].minter));
                gang[x].push_back(pair<string, int>(array[i].n2, array[i].minter));
                weight[x] += array[i].minter;
                array[i].con = 1;
                number++;
                ji += 2;
            } else {
                int t1 = 0, t2 = 0;
                for (int k = 0; k < ji; k++) {
                    if (array[i].n1 == gang[x][k].first) {
                        gang[x][k].second += array[i].minter;
                        t1 = 1;
                    }
                    if (array[i].n2 == gang[x][k].first) {
                        gang[x][k].second += array[i].minter;
                        t2 = 1;
                    }
                }
                if (t1 == 1 && t2 == 0) {
                    ji++;
                    gang[x].push_back(pair<string, int>(array[i].n2, array[i].minter));
                } else if (t1 == 0 && t2 == 1) {
                    ji++;
                    gang[x].push_back(pair<string, int>(array[i].n1, array[i].minter));
                }
                if (t1 == 1 || t2 == 1) {
                    number++;
                    array[i].con = 1;
                    weight[x] += array[i].minter;
                    break;
                }
            }
        }
        if (number == 0) {
            ji = 0;
            x++;
        }
    }
    vector<pair<string, int>> ok;
    for (int i = 0; i < gang->size(); i++) {
        if (gang[i].size() > 2 && weight[i] > k) {
            sort(gang[i].begin(), gang[i].end(), comp1);
            ok.push_back(pair<string, int>(gang[i][0].first, gang[i].size()));
        }
    }
    sort(ok.begin(), ok.end(), comp2);
    cout << ok.size() << endl;
    for (int i = 0; i < ok.size(); i++) {
        cout << ok[i].first << " " << ok[i].second << endl;
    }
}

#include<iostream>
#include<string>
#include<map>
using namespace std;
const int maxn=2010;

map<int,string>intToString;
map<string,int>stringToInt;
map<string,int>Gang;
int G[maxn][maxn]={0},weight[maxn]={0};
int n,k,numPerson=0;
bool vis[maxn]={false};

void DFS(int nowVisit,int& head,int& numMember,int& totalValue){
	numMember++;
	vis[nowVisit]=true;
	if(weight[nowVisit]>weight[head]){
		head=nowVisit;
	}
	for(int i=0;i<numPerson;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);
			}
		}
	}
}


void DFSTrave(){
	for(int i=0;i<numPerson;i++){
		if(vis[i]==false){
			int head=i,numMember=0,totalValue=0;
			DFS(i,head,numMember,totalValue);
			if(numMember>2&&totalValue>k){
				Gang[intToString[head]]=numMember;
			}
		}
	}
}


int change(string str){
	if(stringToInt.find(str)!=stringToInt.end()){
		return stringToInt[str];
	}else{
		stringToInt[str]=numPerson;
		intToString[numPerson]=str;
		return numPerson++;
	}
}

int main(){
	int 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;
	}
	DFSTrave();
	cout<<Gang.size()<<endl;
	map<string,int>::iterator it;
	for(it=Gang.begin();it!=Gang.end();it++){
		cout<<it->first<<" "<<it->second<<endl;
	}
	return 0;
}

a = list(map(int,input().split()))
d = {};m = [];n = [0 for i in range(a[0])]
for i in range(a[0]):
    b = input().split()
    f = 0;j = 0
    for k in range(2):
        d[b[k]] = d[b[k]] + int(b[2]) if b[k] in d else int(b[2])
    while j < len(m):
        if set([b[0],b[1]]) & m[j]:
            if f:
                m[f2] |= m[j];del m[j]
                n[f2] += n[j];del n[j]
                continue
            else:
                m[j] |= set([b[0],b[1]])
                n[j] += int(b[2])
                f = 1;f2 = j
        j += 1
    else:
        if f == 0:
            m.append(set([b[0],b[1]]))
            n[j] = int(b[2])
            
p = 0;t = [];i = 0
while i < len(m):
    if len(m[i]) > 2 and n[i] > a[1]:
        p += 1;r = 0
        for j in m[i]:
            if d[j] > r:
                r = d[j];s = j
        t.append(s + ' ' + str(len(m[i])))
    i += 1

print(p)
for i in sorted(t):print(i)

gang = {}
name = {}
index = []
con = 0
n,t = map(int,input().split())
for i in range(n):
    te = input().split()
    if (te[0] not in name) and (te[1] not in name):
        con+=1
        name[te[0]]=[con,int(te[2])]
        name[te[1]]=[con,int(te[2])]
        gang[con]=[int(te[2]),2,te[0],te[1]]      
    elif (te[0] in name) and (te[1] not in name):
        name[te[1]]=[int(name[te[0]][0]),int(te[2])]
        name[te[0]][1]+=int(te[2])
        gang[name[te[0]][0]][0]+=int(te[2])
        gang[name[te[0]][0]][1]+=1
        gang[name[te[0]][0]].append(te[1])
    elif (te[1] in name) and (te[0] not in name):
        name[te[0]]=[int(name[te[1]][0]),int(te[2])]
        name[te[1]][1]+=int(te[2])
        gang[name[te[1]][0]][0]+=int(te[2])###,
        gang[name[te[1]][0]][1]+=1
        gang[name[te[1]][0]].append(te[0])
    elif (te[1] in name) and (te[0] in name) and (name[te[1]][0]==name[te[0]][0]):
        name[te[1]][1]+=int(te[2])
        name[te[0]][1]+=int(te[2])
        gang[name[te[0]][0]][0]+=int(te[2])
    elif (te[1] in name) and (te[0] in name) and (name[te[1]][0]!=name[te[0]][0]):
        name[te[1]][1]+=int(te[2])
        name[te[0]][1]+=int(te[2])
        temp = int(name[te[1]][0])
        gang[name[te[0]][0]][0]+=int(te[2])
        gang[name[te[0]][0]][0]+=int(gang[name[te[1]][0]][0])
        gang[name[te[0]][0]][1]+=int(gang[name[te[1]][0]][1])
        for i in gang[name[te[1]][0]][2:]:
            name[i][0] = int(name[te[0]][0])
            gang[name[te[0]][0]].append(str(i))
        del gang[temp]
outlst = []
for i in gang:
    if gang[i][0]>t and gang[i][1]>2:
        ma = -1
        te = ''
        for j in gang[i][2:]:
            if name[j][1]>ma:
                ma = name[j][1]
                te = j
        outlst.append(te)
print(len(outlst))
outlst.sort()
for i in outlst:
    print(i+" "+str(gang[name[i][0]][1]))

class Graph:
    def __init__(self,L):
        self.i2s,self.s2i=[],{}
        for a,b,c in L:
            if a not in self.s2i:
                self.i2s.append(a)
                self.s2i[a]=len(self.i2s)-1
            if b not in self.s2i:
                self.i2s.append(b)
                self.s2i[b]=len(self.i2s)-1
        self.vn=len(self.i2s)
        self.V=[0]*self.vn
        self.E=[[float('inf')]*self.vn for _ in range(self.vn)]
        for a,b,c in L:
            a,b,c=self.s2i[a],self.s2i[b],int(c)
            self.V[a]+=c
            self.V[b]+=c
            self.E[a][b]=c
            self.E[b][a]=c
    def BFS(self,lim):
        from collections import deque
        visited=[False]*self.vn
        gang,res=[],[]
        def bfs(s,res):
            tmp,Q,total=set([]),deque([s]),0
            while len(Q)>0:
                s=Q.popleft()
                visited[s]=True
                tmp.add(s)
                for i in range(self.vn):
                    if self.E[s][i]<float('inf'):
                        total+=self.E[s][i]
                        self.E[s][i]=float('inf')
                        if i not in tmp:
                            Q.append(i)
            if len(tmp)>=3 and total/2>=lim:
                res.append(tmp)
        for i in range(self.vn):
            if not visited[i]:
                bfs(i,gang)
        print(len(gang))
        for e in gang:
            tmp,a=max((self.V[i],i) for i in e)
            res.append([self.i2s[a],len(e)])
        res.sort()
        for e in res:
            print(e[0],e[1])
N,K=map(int,input().split())
L=list(input().split() for _ in range(N))
G=Graph(L)
G.BFS(K)

写的跟狗屎似的，过两天我自己也看不懂了。结果是正确的。
用java惯了，上来就写类，没有用什么算法。
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;
typedef struct
{
	map<string, int> persons;
	bool find(string nameA, string nameB)
	{
		if(persons.count(nameA)==1 || persons.count(nameB)==1)
			return true;
		return false;
	}
	void addTime(string name, int time)
	{
		if(persons.find(name)!=persons.end())
			persons[name]+=time;
		else
			persons[name]=time;
	}
	string getHead()
	{
		map<string, int>::iterator iter;
		int maxTime=0;
		string head;
		for(iter=persons.begin(); iter!=persons.end(); iter++)
		{
			if(iter->second>maxTime)
			{
				maxTime=iter->second;
				head=iter->first;
			}
		}
		return head;
	}
	int getTotalTime()
	{
		map<string, int>::iterator iter;
		int totalTime=0;
		for(iter=persons.begin(); iter!=persons.end(); iter++)
		{
			totalTime+= iter->second;
		}
		return totalTime/2;
	}
}Gang;
int main()
{
	vector<Gang> gangs;
	vector<Gang>::iterator iter, g;
	map<string, int>::iterator iter2;
	string nameA, nameB;
	int N,K,time,count=0;
	cin>>N>>K;
	while(N--)
	{
		cin>>nameA>>nameB>>time;
		bool flag = false;
		for(iter=gangs.begin(); iter!=gangs.end();iter++)
		{
			if(iter->find(nameA, nameB))
			{
				if(!flag)
				{
					g= iter;
					g->addTime(nameA, time);
					g->addTime(nameB, time);
				}				
				else
				{
					for(iter2=iter->persons.begin(); iter2!=iter->persons.end(); iter2++)
					{
						g->addTime(iter2->first, iter2->second);
					}
					iter = gangs.erase(iter);
					iter--;
					g->addTime(nameA, time);
					g->addTime(nameB, time);
				}
				flag = true;
			}	
		}
		if(!flag)
		{
			Gang g;
			g.addTime(nameA, time);
			g.addTime(nameB, time);
			gangs.push_back(g);
		}
	}
	for(iter=gangs.begin(); iter!=gangs.end();)
	{
		if(iter->persons.size()<=2 || iter->getTotalTime()<=K)
		{
			iter = gangs.erase(iter);
		}
		else
			iter++;
	}
	cout<<gangs.size()<<endl;
	map<string, int> heads;
	for(iter=gangs.begin(); iter!=gangs.end(); iter++)
	{
		heads[iter->getHead()] = iter->persons.size();
	}
	for(iter2=heads.begin(); iter2!=heads.end(); iter2++)
	{
		cout<<iter2->first<<" "<<iter2->second<<endl;
	}
	return 0;
}

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

const int N = 1024, K = 1024, M = 20000;
int n, k;
int e[N][N], w[N], num[M], cnt;
int head[N], nMem[N];
char name[K][4];
inline int stoint(char *s)
{
    return (s[0]==0 ? 0 : s[0] - 'A' + 1) * 729 + \
    (s[1]==0 ? 0 : s[1] - 'A' + 1) * 27 + \
    (s[0]==0 ? 0 : s[0] - 'A' + 1);
}
bool Comp(int a, int b)
{
    return strcmp(name[head[a]], name[head[b]]) < 0;
}
int main()
{
    memset(num, -1, sizeof(num));
    memset(e, 0, sizeof(e));
    memset(w, 0, sizeof(w));
    cnt = 0;
    scanf("%d%d\n", &n, &k);
    k = k * 2;
    for(int i = 0; i < n; i++) {
        char a[4],b[4];
        int t;
        scanf("%s %s %d\n", a, b, &t);
        int u = stoint(a), v = stoint(b);
        if(num[u] == -1) {
            num[u] = cnt;
            memcpy(name[cnt++], a, sizeof(a));
        }
        if(num[v] == -1) {
            num[v] = cnt;
            memcpy(name[cnt++], b, sizeof(b));
        }
        e[num[u]][num[v]] = e[num[v]][num[u]] = 1;
        w[num[u]] += t;
        w[num[v]] += t;
    }

    int color = 0;
    int vis[N];
    memset(vis, -1, sizeof(vis));
    for(int i = 0; i < cnt; i++) { //flood fill
        if(vis[i] != -1)
            continue;
        queue<int> q;
        q.push(i);
        vis[i] = color;
        int nNode = 0, total = 0;
        head[color] = i;
        while(!q.empty()) {
            int u = q.front(); q.pop();
            nNode++;
            total += w[u];
            if(w[u] > w[head[color]])
                head[color] = u;
            for(int k = 0; k < cnt; k++)
                if(e[u][k] && vis[k] == -1) {
                    vis[k] = color;
                    q.push(k);
                }
        }
        if(nNode > 2 && total > k) {
            nMem[color] = nNode;
            color++;
        }
    }
    printf("%d\n", color);
    int idx[N];
    for(int i = 0; i < color; i++)
        idx[i] = i;
    sort(idx, idx + color, Comp);
    for(int i = 0; i < color; i++) {
        printf("%s %d\n", name[head[idx[i]]], nMem[idx[i]]);
    }
    return 0;
}

#include<bits/stdc++.h>

using namespace std;
vector<map<string, int> >  Gangs;

int  Weight(map<string, int>& members)
{
    int w(0);
    for(auto iter = members.begin(); iter!=members.end(); ++iter)
        w += iter->second;
    return w/2;
}
string Head(map<string, int>& members)
{
    string max_("");
    for(auto iter = members.begin(); iter!=members.end(); ++iter)
    {
        if(iter==members.begin()||iter->second > members[max_])
            max_ = iter->first;
    }
    return max_;
}

int main()
{
    //freopen("infile.txt", "r", stdin);
    int N,K;
    cin>>N>>K;
    for(int n=0,w; n<N; ++n)
    {
        string m1, m2;
        cin>>m1>>m2>>w;

        //insert
        {
            map<string, int>::iterator iter;
            unsigned int i=0,j=0,flag1(1),flag2(1);
            for(; i<Gangs.size(); ++i)
            {
                for(iter=Gangs[i].begin(); iter!=Gangs[i].end(); ++iter)
                    if(iter->first==m1)
                    {
                        flag1 = 0;
                        break;
                    }
                if(flag1==0)
                    break;
            }
            for(; j<Gangs.size(); ++j)
            {
                for(iter=Gangs[j].begin(); iter!=Gangs[j].end(); ++iter)
                    if(iter->first==m2)
                    {
                        flag2 = 0;
                        break;
                    }
                if(flag2==0)
                    break;
            }

            if(flag1&&flag2)
            {
                map<string, int> t;
                t[m1] = w;
                t[m2] = w;
                Gangs.push_back(t);
            }
            else if(flag1 != flag2)
            {
                if(flag1)
                    i = j;
                Gangs[i][m2] += w;
                Gangs[i][m1] += w;
            }
            else if(i==j)
            {
                Gangs[i][m2] += w;
                Gangs[i][m1] += w;
            }
            else //merge
            {
                Gangs[i][m1] += w;
                Gangs[j][m2] += w;
                Gangs[i].insert(Gangs[j].begin(),Gangs[j].end());
                auto iter = Gangs.begin();
                while(j--)
                    ++iter;
                Gangs.erase(iter);
            }
        }
    }

    map<string,int> Output;
    for(unsigned i=0;i<Gangs.size();++i)
    {
        if(Gangs[i].size()>2&&Weight(Gangs[i])>K)
            Output[Head(Gangs[i])] = Gangs[i].size();
    }
    cout<<Output.size()<<endl;
    for(auto iter=Output.begin();iter!=Output.end();++iter)
            cout<<iter->first<<" "<<iter->second<<endl;
    return 0;
}