当前位置: 首页 > news >正文

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

【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;
}

相关文章:

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

【PAT甲级题解记录】1034 Head of a Gang (30 分) 前言 Problem&#xff1a;1034 Head of a Gang (30 分) Tags&#xff1a;图的遍历 连通分量统计 DFS Difficulty&#xff1a;剧情模式 想流点汗 想流点血 死而无憾 Address&#xff1a;1034 Head of a Gang (30 分) 问题描述 …...

Python搭建一个steam钓鱼网站,只要免费领游戏,一钓一个准

前言 嗨喽~大家好呀&#xff0c;这里是魔王呐 ❤ ~! 我们日常上网的时候&#xff0c;总是会碰到一些盗号的网站&#xff0c;或者是别人发一些链接给你&#xff0c; 里面的内容是一些可以免费购物网站的优惠券、游戏官网上可以免费领取皮肤、打折的游戏。 这些盗号网站统一的目…...

maven 私服nexus安装与使用

一、下载nexus Sonatype公司的一款maven私服产品 1、官网下载地址&#xff1a;https://help.sonatype.com/repomanager3/product-information/download 2、csdn下载地址&#xff1a;https://download.csdn.net/download/u010197591/87522994 二、安装与配置 1、下载后解压如…...

详解数据结构中的顺序表的手动实现,顺序表功能接口【数据结构】

文章目录线性表顺序表接口实现尾插尾删头插头删指定位置插入指定位置删除练习线性表 线性表&#xff08;linear list&#xff09;是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构&#xff0c;常见的线性表&#xff1a;顺序表、链表、栈、队列…...

【二】kubernetes操作

k8s卸载重置 名词解释 1、Namespace&#xff1a;名称用来隔离资源&#xff0c;不隔离网络 创建名称空间 一、命名空间namesapce 方式一&#xff1a;命令行创建 kubectl create ns hello删除名称空间 kubectl delete ns hello查询指定的名称空间 kubectl get pod -n kube-s…...

如何在 C++ 中调用 python 解析器来执行 python 代码(五)?

本节研究如何对 import 做白名单 目录 如何在 C 中调用 python 解析器来执行 python 代码&#xff08;一&#xff09;&#xff1f;如何在 C 中调用 python 解析器来执行 python 代码&#xff08;二&#xff09;&#xff1f;如何在 C 中调用 python 解析器来执行 python 代码&…...

八 SpringMVC【拦截器】登录验证

目录&#x1f6a9;一 SpringMVC拦截器✅ 1.配置文件✅2.登录验证代码&#xff08;HandlerInterceptor&#xff09;✅3.继承HandlerInterceptorAdapter&#xff08;不建议使用&#xff09;✅4.登录页面jsp✅5.主页面&#xff08;操作页面&#xff09;✅6.crud用户在访问页面时 只…...

PhotoShop基础使用

49&#xff1a;图片分类 1&#xff1a;像素图 特点&#xff1a;放大后可见&#xff0c;右一个个色块&#xff08;像素&#xff09;组合而成。 优点&#xff1a;容量小&#xff0c;纯天然 JPG、JPEG、png、GIF 2&#xff1a;矢量图 面向对象图像 绘图图像 特点&#xff1a;不…...

借助阿里云 AHPA,苏打智能轻松实现降本增效

作者&#xff1a;元毅 “高猛科技已在几个主要服务 ACK 集群上启用了 AHPA。相比于 HPA 的方案&#xff0c;AHPA 的主动预测模式额外降低了 12% 的资源成本。同时 AHPA 能够提前资源预热、自动容量规划&#xff0c;能够很好的应对突发流量。” ——赵劲松 (高猛科技高级后台工…...

美团2面:如何保障 MySQL 和 Redis 数据一致性?这样答,让面试官爱到 死去活来

美团2面&#xff1a;如何保障 MySQL 和 Redis 的数据一致性&#xff1f; 说在前面 在尼恩的&#xff08;50&#xff09;读者社群中&#xff0c;经常遇到一个 非常、非常高频的一个面试题&#xff0c;但是很不好回答&#xff0c;类似如下&#xff1a; 如何保障 MySQL 和 Redis…...

react hooks学习记录

react hook学习记录1.什么是hooks2.State Hook3.Effect Hook4.Ref Hook1.什么是hooks (1). Hook是React 16.8.0版本增加的新特性/新语法 (2). 可以让你在函数组件中使用 state 以及其他的 React 特性 貌似现在更多的也是使用函数式组件的了&#xff0c;重要 2.State Hook imp…...

创新型中小企业认定评定标准

一、公告条件评价得分达到 60 分以上&#xff08;其中创新能力指标得分不低于 20 分、成长性指标及专业化指标得分均不低于 15 分&#xff09;&#xff0c;或满足下列条件之一&#xff1a;&#xff08;一&#xff09;近三年内获得过国家级、省级科技奖励。&#xff08;二&#…...

记录一次nginx转发代理skywalking白屏 以及nginx鉴权配置

上nginx代码 #user nobody; worker_processes 1; #error_log logs/error.log; #error_log logs/error.log notice; #error_log logs/error.log info; #pid logs/nginx.pid; events { worker_connections 1024; } http { include mime.types; …...

如何使用FarsightAD在活动目录域中检测攻击者部署的持久化机制

关于FarsightAD FarsightAD是一款功能强大的PowerShell脚本&#xff0c;该工具可以帮助广大研究人员在活动目录域遭受到渗透攻击之后&#xff0c;检测到由攻击者部署的持久化机制。 该脚本能够生成并导出各种对象及其属性的CSV/JSON文件&#xff0c;并附带从元数据副本中获取…...

Python - 操作txt文件

文章目录打开txt文件读取txt文件写入txt文件删除txt文件打开txt文件 open(file, moder, bufferingNone, encodingNone, errorsNone, newlineNone, closefdTrue)函数用来打开txt文件。 #方法1&#xff0c;这种方式使用后需要关闭文件 f open("data.txt","r&qu…...

老杜MySQL入门基础 1

1 数据库&#xff1a;DataBase(存储数据的仓库) 2 数据库管理系统&#xff1a;DataBaseManagementSystem(DBMS)(管理数据库中的数据的) DBMS可以对数据库中的数据进行增删改查常见的数据库管理系统&#xff1a;MySQL、Oracle、SQLserver 3 SQL&#xff1a;结构化查询语言 编…...

Vue中splice的使用

splice(index,len,[item])它也可以用来替换/删除/添加数组内某一个或者几个值&#xff08;该方法会改变原始数组&#xff09; index:数组开始下标 len: 替换/删除的长度 item:替换的值&#xff0c;删除操作的话 item为空 删除&#xff1a; //删除起始下标为1&…...

Ubuntu通过rsync和inotify实现双机热备

Rsync Inotify双机热备 一、备份机操作 备份机&#xff1a;主服务器或主机文件将需要备份的文件同步到此服务器上&#xff0c;即从主服务器上同步过来进行备份。 1.1安装rsync sudo apt-get install rsync1.2修改/etc/dault/rsync文件 sudo vim /etc/default/rsync修改如…...

【python】异常详解

注&#xff1a;最后有面试挑战&#xff0c;看看自己掌握了吗 文章目录错误分类捕捉异常实例finally的使用捕捉特定异常抛出异常用户自定义异常&#x1f338;I could be bounded in a nutshell and count myself a king of infinite space. 特别鸣谢&#xff1a;木芯工作室 、I…...

pc、移动端自适应css

第一步按照vant官网给的rem适配&#xff0c;安装 postcss-pxtorem&#xff1a;npm install postcss-pxtorem&#xff1b; 第二步安装lib-flexible&#xff1a;npm i -S amfe-flexible&#xff0c;记得在main.js文件引入 import ‘amfe-flexible’&#xff1b; 第三步进行 postc…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...

WebRTC从入门到实践 - 零基础教程

WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC&#xff1f; WebRTC&#xff08;Web Real-Time Communication&#xff09;是一个支持网页浏览器进行实时语音…...

永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器

一、原理介绍 传统滑模观测器采用如下结构&#xff1a; 传统SMO中LPF会带来相位延迟和幅值衰减&#xff0c;并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF)&#xff0c;可以去除高次谐波&#xff0c;并且不用相位补偿就可以获得一个误差较小的转子位…...

实战三:开发网页端界面完成黑白视频转为彩色视频

​一、需求描述 设计一个简单的视频上色应用&#xff0c;用户可以通过网页界面上传黑白视频&#xff0c;系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观&#xff0c;不需要了解技术细节。 效果图 ​二、实现思路 总体思路&#xff1a; 用户通过Gradio界面上…...

Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么&#xff1f;它的作用是什么&#xff1f; Spring框架的核心容器是IoC&#xff08;控制反转&#xff09;容器。它的主要作用是管理对…...

链式法则中 复合函数的推导路径 多变量“信息传递路径”

非常好&#xff0c;我们将之前关于偏导数链式法则中不能“约掉”偏导符号的问题&#xff0c;统一使用 二重复合函数&#xff1a; z f ( u ( x , y ) , v ( x , y ) ) \boxed{z f(u(x,y),\ v(x,y))} zf(u(x,y), v(x,y))​ 来全面说明。我们会展示其全微分形式&#xff08;偏导…...