# PAT 解题报告 1034. Head of a Gang (30)

### 题目描述：

One way that the police finds the head of a gang is to check people’s phone calls. If there is a phone call between A and B, we say that A and B is related. The weight of a relation is defined to be the total time length of all the phone calls made between the two persons. A “Gang” is a cluster of more than 2 persons who are related to each other with total relation weight being greater than a given threthold K. In each gang, the one with maximum total weight is the head. Now given a list of phone calls, you are supposed to find the gangs and the heads.

### 算法分析：

```#include <iostream>

#include <cstdio>
#include <cstring>

#include "stdio.h"

#include "math.h"
#include <algorithm>
#include <vector>
#include <map>

#include <iomanip>

#define MAX(a,b) (a>b)?a:b
#define REP(i,n) for(i=0;i<(n);++i)

#define NNodes 2010
using namespace std;

typedef struct {
string name;
int wgt;
} Member;

Member members[NNodes];
Member res[1000];

map<string, int> names;

int disJointSet[NNodes];
int classes;

int N, K;

void dfsUnion(int root, int N, int *count, int *total, int* head) {
disJointSet[root] = classes;
(*count) = (*count) + 1;
for(int i=1; i<=N; i++) {
}

}
for(int i=1; i<=N; i++)
{
}
}
}

int compare(const void *elem1, const void *elem2)
{
return (((Member*)(elem1))->name).compare(((Member*)(elem2))->name);
}

int main(void) {
cin>>N>>K;
int id = 0;
for(int i=0; i<N; i++) {
string a; string b; int weight;
cin>>a>>b>>weight;
if(!names[a])
names[a] = ++id;
if(!names[b])
names[b] = ++id;

members[names[a]].name = a; members[names[a]].wgt += weight;
members[names[b]].name = b; members[names[b]].wgt += weight;
}

memset(disJointSet, 0, sizeof(int)*NNodes);
classes = 0;
int len = 0;
for(int i=1; i<=id; i++) {
if(!disJointSet[i]) {
int numOfMem = 0;
int totalWeight = 0;

classes++;
if(numOfMem>2 && totalWeight/2>K) {
res[len++].wgt = numOfMem;
}
}
}
if(len) {
qsort(res, len, sizeof(Member), compare);
cout<<len<<endl;
for(int j=0; j<len; j++) {
cout<<res[j].name<<" "<<res[j].wgt<<endl;
}
}
else {
cout<<0<<endl;
}
return 0;

}
```
Written on August 3, 2013