【PAT甲级题解记录】1034 Head of a Gang (30 分)

前言

Problem：1034 Head of a Gang (30 分)

Tags：图的遍历 连通分量统计 DFS

Difficulty：剧情模式 想流点汗 想流点血 死而无憾

Address：1034 Head of a Gang (30 分)

问题描述

给定一组通话记录，包含通话双方和通话时间。已知帮派成员内部通过电话联系，可根据通话记录来判断每个人是否在某个帮派。

确认一个帮派的条件是

• 帮派之间总的通话时间超过K
• 帮派人数必须大于2

题意略复杂，建议多读一遍搞清楚，然后可以抽象出题目的意思：

一个无向带权图中有多个连通分量，若某一个连通分量中边权之和大于给定值K，并且其中点数大于2，则可以视为一个帮派，其中带权出入度最大的点就是老大。要求输出所有帮派的信息（包括帮派老大、帮派人数）。

解题思路

将题意抽象后就显得比较简单了，搞一些容器来存储这个图，完了dfs遍历一遍这张图，找出所有连通分支，统计保存好各个连通分支的数据，完了输出就好。

但题目的输入有点烦，他并不是一个传统的图的输入，而是输入了若干条边，其中边是有重复的需要累加，最糟糕的是点没有用0-N的数字表示而是用了string型的name。针对此，我们可以设置两个map来完成name to id和id to name的映射，然后再输入时做一些处理即可。当然要用指针、数据结构来写一个图也许也能做到，但是有重复边等问题我觉得还是太麻烦了。

参考代码

//
// Created by WU on 2023/3/2.
//
#include<bits/stdc++.h>using namespace std;int N, K;
map<string, int> toId;  // 人名转数字id
map<int, string> toName;  // 数字id转人民
int edges[2005][2005];  // 邻接矩阵（注意题目中给出的范围1000指的是通话数，每一对通话对象都有两个人，所以需要开2000，否则会有一个测试点段错误）
vector<int> weight(2005, 0);  // 个人通话量，一个帮派中weight最大的时老大
int counts;  // 输入时每当遇到一个没出现过的人名，都要将其转换为数字id，counts就用来计数表示当前已经有多少id了void init() {cin >> N >> K;counts = 0;for (int i = 0; i < N; ++i) {string name1, name2;int tel_time;cin >> name1 >> name2 >> tel_time;// initialize name&idif (!toId.count(name1)) {toId[name1] = counts;toName[counts++] = name1;}if (!toId.count(name2)) {toId[name2] = counts;toName[counts++] = name2;}edges[toId[name1]][toId[name2]] += tel_time;edges[toId[name2]][toId[name1]] += tel_time;weight[toId[name1]] += tel_time;weight[toId[name2]] += tel_time;}
}vector<int> visited(1005, 0);  // 访问标记，1表示已经访问过，用来辅助dfs
// 动态更新当前的最大通话量的所属id、最大通话量、本帮派人数
int max_id;
int weight_sum;
int gang_cnt;void dfs(int root) {// update infovisited[root] = 1;weight_sum += weight[root]; // 注意这里多加了，一会需要减半gang_cnt++;if (weight[root] > weight[max_id]) {max_id = root;}// continue dfsfor (int i = 0; i < N; i++) {if (edges[root][i] && !visited[i]) {dfs(i);}}
}// 为了方便统计和输出帮派信息，干脆建了个结构体
struct Gang {int head_id; // 帮主idstring head_name;int weight_sum; // 帮派的总通话时间int cnt; // 帮派人数Gang(int _head_id, string _head_name, int _weight_sum, int _cnt) : head_id(_head_id), head_name(_head_name),weight_sum(_weight_sum), cnt(_cnt) {}bool operator<(const Gang &gang) const {return head_name < gang.head_name;}
};int main() {init();vector<Gang> gangs;for (int i = 0; i < N; i++) {if (!visited[i]) {// initialize temporary variable for dfsmax_id = i;weight_sum = 0; // 初始化当前帮派的总通话时间，注意需要在dfs时用点来累加，不能用边，因为dfs不会遍历所有边gang_cnt = 0;// dfsdfs(i);// add a gangif (weight_sum / 2 > K && gang_cnt > 2) {gangs.emplace_back(max_id, toName[max_id], weight_sum / 2, gang_cnt);}}}sort(gangs.begin(), gangs.end());cout << gangs.size() << endl;for (int i = 0; i < int(gangs.size()); ++i) {cout << gangs[i].head_name << " " << gangs[i].cnt << endl;}return 0;
}