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

第三章 图论 No.13拓扑排序

文章目录

      • 裸题:1191. 家谱树
      • 差分约束+拓扑排序:1192. 奖金
      • 集合+拓扑序:164. 可达性统计
      • 差分约束+拓扑序:456. 车站分级

拓扑序和DAG有向无环图联系在一起,通常用于最短/长路的线性求解
image.png

裸题:1191. 家谱树

1191. 家谱树 - AcWing题库
image.png

#include <iostream>
#include <cstring>
using namespace std;const int N = 110, M = 10010;
int h[N], e[M], ne[M], idx;
int d[N], q[N], hh, tt = -1;
int n, m;void add(int x, int y)
{e[idx] = y, ne[idx] = h[x], h[x] = idx ++ ;
}void topsort()
{for (int i = 1; i <= n; ++ i )if (!d[i]) q[ ++ tt ] = i;while (tt >= hh ){int x = q[hh ++ ];for (int i = h[x]; i != -1; i = ne[i]){int y = e[i];if (-- d[y] == 0) q[++ tt] = y;}}
}int main()
{memset(h, -1, sizeof(h));scanf("%d", &n);for (int x = 1; x <= n; ++ x ){int y;while (scanf("%d", &y), y){add(x, y);d[y] ++ ;}}topsort();for (int i = 0; i <= tt; ++ i )printf("%d ", q[i]);return 0;
}

差分约束+拓扑排序:1192. 奖金

1192. 奖金 - AcWing题库
image.png

由于图中所有边权都是正数,可以直接使用topsort求解差分约束问题
根据题意,要求一个最小值,使用最长路求解,转化题目的条件: A > = B + 1 A >= B + 1 A>=B+1 x i > = x 0 + 100 x_i >= x_0 + 100 xi>=x0+100
x 0 x_0 x0为一个虚拟源点,向每个点连了一条权值为100的边

若图中存在环,topsort的队列长度将小于n,因为环的起点无法进入队列
先用topsort判断图中是否存在环,若不存在,根据拓扑序遍历图,求解最长路

#include <iostream>
#include <cstring>
using namespace std;const int N = 10010, M = 30010;
int h[N], e[M], ne[M], w[M], idx;
int q[N], d[N], hh, tt = -1;
int dis[N];
int n, m;void add(int x, int y, int d)
{e[idx] = y, ne[idx] = h[x], w[idx] = d, h[x] = idx ++ ;
}bool topsort()
{q[ ++ tt ] = 0;while (tt >= hh){int x = q[hh ++ ];for (int i = h[x]; i != -1; i = ne[i] ){int y = e[i];if ( -- d[y] == 0) q[ ++ tt ] = y;}}return tt == n;
}int main()
{memset(h, -1, sizeof(h));scanf("%d%d", &n, &m);for (int i = 0; i < m; ++ i ){int x, y;scanf("%d%d", &x, &y);add(y, x, 1);d[x] ++ ;}for (int i = 1; i <= n; ++ i ) add(0, i, 100), d[i] ++ ;if (!topsort()) puts("Poor Xed");else {for (int k = 0; k <= tt; ++ k ){int x = q[k];for (int i = h[x]; i != -1; i = ne[i]){int y = e[i];dis[y] = max(dis[y], dis[x] + w[i]);}}int sum = 0;for (int i = 1; i <= n; ++ i ) sum += dis[i];printf("%d\n", sum);}return 0;
}

debug:最后的遍历没有按照拓扑序

for (int x = 0; x <= tt; ++ x )
{for (int i = h[x]; i != -1; i = ne[i]){int y = e[i];dis[y] = max(dis[y], dis[x] + w[i]);}
}

集合+拓扑序:164. 可达性统计

[164. 可达性统计 - AcWing题库](https://www.acwing.com/problem/content/description/166/
image.png

从集合的角度思考, f ( i ) f(i) f(i)表示i这个点能到达的所有点,i首先能到达自己,其次能达到 f ( j 1 ) , f ( j 2 ) , . . . , f ( j n ) f(j_1), f(j_2), ... , f(j_n) f(j1),f(j2),...,f(jn),假设i与n个点直接相连
那么要求 f ( i ) f(i) f(i),就必须求出 f ( j 1 ) , f ( j 2 ) , . . . , f ( j n ) f(j_1), f(j_2), ... , f(j_n) f(j1),f(j2),...,f(jn),即拓扑排序中位于i之后的所有点的 f ( j ) f(j) f(j)
所以这题先拓扑排序,再根据拓扑排序的逆序,求 f ( i ) f(i) f(i)
如何表示集合 f ( i ) f(i) f(i)?用STL的容器bitset,假设图中有N个点,那么bitset的长度为N,每个点都用一个bitset记录其集合,1表示i能递达这个点,0表示不能递达
那么 f ( i ) = f ( j 1 ) ∩ f ( j 2 ) ∩ . . . ∩ f ( j n ) f(i) = f(j_1)∩ f(j_2)∩ ...∩f(j_n) f(i)=f(j1)f(j2)...f(jn)

关于bitset的使用,bitset之间支持|=运算,count()输出bitset中1的个数

#include <iostream>
#include <cstring>
#include <bitset>
using namespace std;const int N = 30010, M = N;
int h[N], e[M], ne[M], idx;
int q[N], d[N], hh, tt = -1;
bitset<N> f[N];
int n, m;void add(int x, int y)
{e[idx] = y, ne[idx] = h[x], h[x] = idx ++ ;
}void topsort()
{for (int i = 1; i <= n; ++ i )if (!d[i]) q[ ++ tt ] = i;while (tt >= hh){int x = q[hh ++ ];for (int i = h[x]; i != -1; i = ne[i]){int y = e[i];if ( -- d[y] == 0) q[ ++ tt ] = y;}}
}int main()
{memset(h, -1, sizeof(h));scanf("%d%d", &n, &m);for (int i = 0; i < m; ++ i ){int x, y;scanf("%d%d", &x, &y);add(x, y);d[y] ++ ;}topsort();for (int i = tt; i >= 0; -- i ){int x = q[i];f[x][x] = 1;for (int i = h[x]; i != -1; i = ne[i]){int y = e[i];f[x] |= f[y];}}for (int i = 1; i <= n; ++ i ) printf("%d\n", f[i].count());return 0;
}

差分约束+拓扑序:456. 车站分级

456. 车站分级 - AcWing题库
image.png

分析题意:对于每一条路线,未经过的站点的等级一定小于经过的站点等级,并且最低的站点等级为1级
题目要求所有等级划分中的最少等级数,用最长路求最小值。将以上条件转换成差分约束中的两个条件: B > = A + 1 B >= A + 1 B>=A+1, x i > = x 0 + 1 x_i >= x_0 + 1 xi>=x0+1
x 0 x_0 x0为虚拟源点,通过 x 0 x_0 x0能到达图中的所有点,那么就一定能递达所有边

由于每条路线路都会建立n * m条边,极端情况下可能会爆空间,所以考虑如何优化
一条路径中未经过的站点将向经过的站点连接一条权值为1的边,一共n * m条,由于这些边的权值相同,可以在这些边中创建一个虚拟点v,未经过的点分别向v连一条权值为0的边,v向经过的点分别连接一条权值为1的边。这样,从未经过的点到经过的点的权值和依然为1,但是需要建立的边数为n + m,此时的边数在极端情况下也不会爆空间

#include <iostream>
#include <cstring>
using namespace std;const int N = 2010, M = 1e6 + 10;
int h[N], e[M], ne[M], w[M], idx;
int d[N], q[N], hh, tt = -1;
bool st[N]; int dis[N];
int n, m;void add(int x, int y, int d)
{e[idx] = y, ne[idx] = h[x], w[idx] = d, h[x] = idx ++ ;
}void topsort()
{for (int i = 1; i <= n + m; ++ i ) if (!d[i]) q[ ++ tt ] = i;while (tt >= hh){int x = q[hh ++ ];for (int i = h[x]; i != -1; i = ne[i]){int y = e[i];if (-- d[y] == 0) q[ ++ tt ] = y;}}
}int main()
{memset(h, -1, sizeof(h));scanf("%d%d", &n, &m);for (int i = 1; i <= m; ++ i ){memset(st, false, sizeof(st));int t, start = n, end = 0;scanf("%d", &t);while (t -- ){int x;scanf("%d", &x);st[x] = true;start = min(start, x), end = max(end, x);}int v = n + i;for (int i = start; i <= end; ++ i ){if (st[i]) add(v, i, 1), d[i] ++ ;else add(i, v, 0), d[v] ++ ;}}topsort();for (int i = 1; i <= n; ++ i ) dis[i] = 1;for (int i = 1; i <= tt; ++ i ){int x = q[i];for (int i = h[x]; i != -1; i = ne[i]){int y = e[i];dis[y] = max(dis[y], dis[x] + w[i]);}}int res = 0;for (int i = 1; i <= n; ++ i ) res = max(res, dis[i]);printf("%d\n", res);return 0;
}

debug:w[M]写成了w[N],又是这样,然后debug了半天,了

相关文章:

第三章 图论 No.13拓扑排序

文章目录 裸题&#xff1a;1191. 家谱树差分约束拓扑排序&#xff1a;1192. 奖金集合拓扑序&#xff1a;164. 可达性统计差分约束拓扑序&#xff1a;456. 车站分级 拓扑序和DAG有向无环图联系在一起&#xff0c;通常用于最短/长路的线性求解 裸题&#xff1a;1191. 家谱树 119…...

喜报 | 擎创再度入围IDC中国FinTech 50榜单

8月16日&#xff0c;2023年度“IDC中国FinTech 50”榜单正式揭晓&#xff0c;擎创科技继2022年入选该榜单后&#xff0c;再次以创新者姿态成功入选&#xff0c;并以技术赋能业务创新&#xff0c;成为中国金融科技领域创新与活力的重要贡献者。 “IDC中国FinTech 50”旨在评选出…...

【C++ 记忆站】引用

文章目录 一、引用概念二、引用特性1、引用在定义时必须初始化2、一个变量可以有多个引用3、引用一旦引用一个实体&#xff0c;再不能引用其他实体 三、常引用四、使用场景1、做参数1、输出型参数2、大对象传参 2、做返回值1、传值返回2、传引用返回 五、传值、传引用效率比较六…...

Hlang--用Python写个编程语言-变量的实现

文章目录 前言语法规则表示次幂实现变量实现优先级实现步骤解析关键字语法解析解释器总结前言 先前的话,我们终于是把我们整个架子搭起来了,这里重复一下我们的流程,那就是,首先,我们通过解析文本,然后呢遍历文本当中的我们定义的合法关键字,然后呢,把他们封装为一个T…...

多维时序 | MATLAB实现PSO-CNN-BiLSTM多变量时间序列预测

多维时序 | MATLAB实现PSO-CNN-BiLSTM多变量时间序列预测 目录 多维时序 | MATLAB实现PSO-CNN-BiLSTM多变量时间序列预测基本介绍模型特点程序设计参考资料 基本介绍 本次运行测试环境MATLAB2021b&#xff0c;MATLAB实现PSO-CNN-BiLSTM多变量时间序列预测。代码说明&#xff1a…...

实现Java异步调用的高效方法

文章目录 为什么需要异步调用&#xff1f;Java中的异步编程方式1. 使用多线程2. 使用Java异步框架 异步调用的关键细节结论 &#x1f389;欢迎来到Java学习路线专栏~实现Java异步调用的高效方法 ☆* o(≧▽≦)o *☆嗨~我是IT陈寒&#x1f379;✨博客主页&#xff1a;IT陈寒的博…...

批量提取文件名到excel,详细的提取步骤

如何批量提取文件名到excel&#xff1f;我们的电脑中可能存储着数量非常多的电子文件&#xff0c;现在需要快速将这些文件的名称全部提取到Excel中。虽然少量数据可以通过复制粘贴的方式轻松完成&#xff0c;但是对于上万个数据而言&#xff0c;复制粘贴都是行不通的&#xff0…...

C#中的泛型约束可以用在以下几个地方?

1.泛型类型参数&#xff1a; 在定义泛型类型或泛型方法时&#xff0c;可以使用泛型约束来限制泛型类型参数的类型。这可以确保类型参数满足特定的条件&#xff0c;从而在编译时捕获错误并提供更安全和可靠的代码。 public class MyClass<T> where T : IComparable<T&…...

Linux Vm上部署Docker

创建ubutu虚拟机并远程连接&#xff0c; 参考 https://blog.csdn.net/m0_48468018/article/details/132267096 在终端中切换到root用户&#xff0c;并安装docker服务 2.1 切换到root用户 sudo su2.2 安装docker服务 , 参考 https://docs.docker.com/engine/install/ubuntu/ …...

ubuntu bind dns服务配置

sudo apt-get install bind9 内网搭建DNS服务器&#xff0c;大多数是解析纯内网地址使用。但是偶尔也需要解析外网的地址&#xff0c;所以我们可以配置DNS没有添加A记录的URL时&#xff0c;forward到外网DNS服务器或者内网的其他DNS服务器解析。 打开配置文件&#xff1a; sud…...

安卓的代码加固和其他安全问题

文章目录 安卓加固apk文件结构dex加固过程 其它安全问题 安卓加固 从App的加固技术来看:主流分为dex加密和so加密,目前来看保护dex文件更为重要,因为dex反编译后的java代码可读性更强。 android-ndk: Native Development Kit 官网解释&#xff1a;这套工具使您能在 Android 应…...

关于Linux Docker springboot jar 日志时间不正确 问题解决

使用Springboot项目的jar&#xff0c;制作了一个Docker镜像&#xff0c;启动该镜像后发现容器和容器中的Springboot 项目的日志时间不正确。 解决 查看容器时间命令为&#xff1a; docker exec 容器id date 1. 容器与宿主机同步时间 在启动镜像时候把操作系统的时间通过&q…...

提高批量爬虫工作效率

大家好&#xff01;作为一名专业的爬虫程序员&#xff0c;我今天要和大家分享一些关于提高批量爬虫工作效率的实用技巧。无论你是要批量采集图片、文本还是视频数据&#xff0c;这些经验都能帮助你在大规模数据采集中事半功倍。废话不多说&#xff0c;让我们开始吧&#xff01;…...

E96系列电阻阻值和代码、乘数对照表

1、为什么要用代码表示&#xff1f; 0805封装还可以简单易懂写下四位丝印&#xff0c;比如10K的1002&#xff0c;但0603的封装上面再想写下四位丝印就没空间了&#xff0c;就算写了也不容易看不清。 2、E96系列电阻阻值和代码、乘数对照表 下面是E96系列的对照表&#xff0c;…...

基于CentOS7.9安装部署docker(简洁版)

安装部署 1基于官方脚本安装&#xff08;不推荐 不能自行选择版本&#xff09; 官方文档&#xff1a;https://docs.docker.com/engine/install/centos/ 2 使用yum安装 阿里云文档&#xff1a;docker-ce镜像_docker-ce下载地址_docker-ce安装教程-阿里巴巴开源镜像站 # ste…...

MySQL常用练手题目

数据库表名和字段设计 1.学生表 Student(s_id,s_name,s_birth,s_sex) 学生编号,学生姓名, 出生年月,学生性别 2.课程表 Course(c_id,c_name,t_id) 课程编号, 课程名称, 教师编号 3.教师表 Teacher(t_id,t_name) 教师编号,教师姓名 4.成绩表 Score (s_id,c_id,s_score) 学生编号…...

Oracle字段长度不足位数补零

Oracle字段长度不足位数补零 有时候从数据库中取出的月份值是1&#xff0c;而不是01&#xff0c;该怎么办呢 SELECTLPAD( CODE_MONTH, 2, 0 ) FROMtb_cube_TY001 WHERECODE_BM_MEATYPE TY20 AND code_measure MYLX01 AND code_month <> ~ AND CODE_ENTITY 01A AND…...

<数据结构与算法>二叉树堆的实现

目录 前言 一、树的概念及结构 1 树的概念 2 树的相关概念 二、二叉树的概念及结构 1.二叉树的概念 2. 特殊的二叉树 3. 二叉树的性质 4.二叉树的存储结构 三、二叉树的顺序结构及实现 1.堆的性质 2.堆的插入 3.堆的实现 堆的结构体 HeapInit 初始化 HeapPush 插入 HeapPop 删…...

FPGA:RS编码仿真过程

FPGA&#xff1a;RS编码仿真过程 RS码是一种纠错性能很强的线性纠错码&#xff0c;能够纠正随机错误和突发错误。RS码是一种多进制BCH码&#xff0c;能够同时纠正多个码元错误。 之前已经记录了在MATLAB中进行rs编解码的过程&#xff0c;现在利用FPGA的IP核实现RS编码的过程&…...

RocketMQ 5.0 架构解析:如何基于云原生架构支撑多元化场景

作者&#xff1a;隆基 本文将从技术角度了解 RocketMQ 的云原生架构&#xff0c;了解 RocketMQ 如何基于一套统一的架构支撑多元化的场景。 文章主要包含三部分内容。首先介绍 RocketMQ 5.0 的核心概念和架构概览&#xff1b;然后从集群角度出发&#xff0c;从宏观视角学习 R…...

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&am…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)

推荐 github 项目:GeminiImageApp(图片生成方向&#xff0c;可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...