Skip to content

Latest commit

 

History

History
82 lines (70 loc) · 3.87 KB

1034. Head of a Gang.md

File metadata and controls

82 lines (70 loc) · 3.87 KB

【PAT A-1034】Head of a Gang

题意概述

警察找到团伙头的一种方法是检查人们的电话。如果 AAA 和 BBB 之间有电话，我们说 AAA 和 BBB 是相关的。关系的权重定义为两个人之间所有电话通话的总时间长度。“帮派”是指由两个以上相互关联的人组成的集群，并且总关联权重大于给定的阈值 K。在每个帮派中，总重量最大的是该帮派的头领。现在给出电话列表，你需要找到帮派和其头领。

输入输出格式

输入第一行均包含两个正数 N 和 K、电话呼叫次数和权重阈值。然后是 N 行，每行以Name1 Name2 Time的格式给出一个电话记录的信息。其中 Name1 和 Name2 是通话两端的人员名称，Time 是通话时间。名称是从 A-Z 中选择的三个大写字母的字符串。时间长度是一个不超过 1000 分钟的正整数。

首先在一行中打印帮派总数。然后，对于每个帮派，在一行中打印头领的名称和成员总数。可以确保每个帮派的头都是唯一的。注意，打印帮派信息时，需根据头领名称的字母顺序对输出进行排序。

数据规模

$$0<N,K<1000$$

算法设计

由于输入的名字是字符串，不好操作，可以将输入的人名全部不重复地存储到vector<string> v中，这样我们就可以通过名字在 v 中的下标来唯一指代这个名字。为了方便找到名字对应的下标，可以在额外使用unordered_map<string, gg> um存储名字和下标的对应关系。换句话说，我们可以利用这个下标对不同的姓名进行编号，这样的编号是从 0 开始连续的。

使用并查集，每一个集合对应于一个帮派。读取每个电话记录时，将电话记录的两个名字所对应的编号所在集合进行合并，并更新相关编号所对应的通话长度。所有电话记录读取完毕后，遍历所有的编号，以集合跟结点作为该集合的唯一标识，更新根结点对应的总通话长度和集合结点个数，此外，为了找到帮派头领，还可以定义一个 head 数组负责追踪帮派中的头领。 所有信息更新完毕，将相关信息按要求进行输出即可。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
const gg MAX = 2005;
vector<gg> ufs(MAX), Time(MAX), num(MAX), totalTime(MAX), head(MAX);
void init() {
    iota(ufs.begin(), ufs.end(), 0);
    iota(head.begin(), head.end(), 0);
}
gg findhead(gg x) { return ufs[x] == x ? x : ufs[x] = findhead(ufs[x]); }
void unionSets(gg a, gg b) { ufs[findhead(a)] = findhead(b); }
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    gg ni, ki, ti;
    string s1, s2;
    cin >> ni >> ki;
    unordered_map<string, gg> um;  //存储姓名和下标的对应关系
    vector<string> v;  //存储所有的名字
    init();
    while (ni--) {
        cin >> s1 >> s2 >> ti;
        if (not um.count(s1)) {
            um.insert({s1, um.size()});
            v.push_back(s1);
        }
        if (not um.count(s2)) {
            um.insert({s2, um.size()});
            v.push_back(s2);
        }
        Time[um[s1]] += ti;
        Time[um[s2]] += ti;
        unionSets(um[s1], um[s2]);  //合并集合
    }
    for (gg i = 0; i < v.size(); ++i) {
        gg r = findhead(i);  //根结点
        ++num[r];  //递增该集合人数
        totalTime[r] += Time[i];  //更新该集合的总通话长度
        if (Time[i] > Time[head[r]]) {  //更新该集合的头领
            head[r] = i;
        }
    }
    vector<pair<string, gg>> ans;
    for (gg i = 0; i < v.size(); ++i) {
        if (i == ufs[i] and num[i] > 2 and totalTime[i] > ki * 2) {
            ans.push_back({v[head[i]], num[i]});
        }
    }
    sort(ans.begin(), ans.end());
    cout << ans.size() << "\n";
    for (auto& i : ans) {
        cout << i.first << " " << i.second << "\n";
    }
    return 0;
}