[PAT解题报告] Head of a Gang
题目给了个很好的背景，就是人物之间打电话。人可以看作节点，边可以看作通话时间，图是无向的。定义一个连通分量可能就是一个团伙，还需要看
（1） 连通分量里的节点数 大于1
（2） 边总权值大于一个阈值K
这个都很简单，我们对于每个点，求连通分量，顺便打上标号（我写的where)就表示它在哪个分量里，按照联通分量标号排序，同一个连通分量的点在一起。求连通分量可以用dfs,顺便求出每个点连边权的总和，也能求出分量里所有边权值和——别忘记除以2和K比较。这样就能找到团伙。排序时同一个团伙把连边权和大的节点放在前面，就能找到每个团伙的头。
还要注意字符串到整数id之间使用map直接映射就好了。
代码：
#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;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1034
