[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

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-28 02:13
门头沟学院_2024
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-15 17:07
途虎_JAVA
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议