[PAT解题报告] Head of a Gang

（1） 连通分量里的节点数 大于1
（2） 边总权值大于一个阈值K

```#include <cstdio>
#include <cstring>
#include <string>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
struct node {
char name[4];
int where;
int weight;
};
map<string,int> id;
int a[2048][2048];
node p[2048];
char s[10];
int n;
set<pair<string,int> > all;
bool cmp(const node &a, const node &b) {
return (a.where < b.where) || ((a.where == b.where) && (a.weight > b.weight));
}
int give(char *name) {
map<string,int>::iterator t = id.find(name);
if (t == id.end()) {
int r = id.size();
strcpy(p[r].name, name);
p[r].weight = 0;
p[r].where = -1;
return id[name] = r;
}
return t->second;
}
void dfs(int x, int y) {
if (p[x].where >= 0) {
return;
}
p[x].where = y;
for (int i = 0; i < n; ++i) {
if (a[x][i]) {
p[x].weight += a[x][i];
dfs(i, y);
}
}
}
int main() {
int k;
scanf("%d%d",&n,&k);
for (int i = 0; i < n; ++i) {
scanf("%s",s);
int x = give(s), len;
scanf("%s%d",s,&len);
int y = give(s);
a[x][y] += len;
a[y][x] += len;
}
n = id.size();
for (int i = 0; i < n; ++i) {
dfs(i, i);
}
sort(p, p + n, cmp);
for (int i = 0; i < n; ) {
int total = 0, j;
for (j = i; (i < n) && (p[j].where == p[i].where); total += p[i++].weight)
;
if ((i - j > 2) && ((total >> 1) > k)) {
all.insert(make_pair((string) p[j].name, i - j));
}
}
printf("%d\n",all.size());
for (set<pair<string,int> >::iterator t = all.begin(); t != all.end(); ++t) {
printf("%s %d\n",t->first.c_str(), t->second);
}
return 0;
}
```

2022-12-28 20:02

2022-12-13 00:19

2022-12-20 22:24

2022-12-09 17:24

2022-12-31 16:55

2022-12-28 02:13

2022-12-17 23:57

2022-12-30 12:08

2022-12-15 17:07