当前位置: 首页 > 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…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...

4. TypeScript 类型推断与类型组合

一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式&#xff0c;自动确定它们的类型。 这一特性减少了显式类型注解的需要&#xff0c;在保持类型安全的同时简化了代码。通过分析上下文和初始值&#xff0c;TypeSc…...

第7篇:中间件全链路监控与 SQL 性能分析实践

7.1 章节导读 在构建数据库中间件的过程中&#xff0c;可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中&#xff0c;必须做到&#xff1a; &#x1f50d; 追踪每一条 SQL 的生命周期&#xff08;从入口到数据库执行&#xff09;&#…...

人工智能--安全大模型训练计划:基于Fine-tuning + LLM Agent

安全大模型训练计划&#xff1a;基于Fine-tuning LLM Agent 1. 构建高质量安全数据集 目标&#xff1a;为安全大模型创建高质量、去偏、符合伦理的训练数据集&#xff0c;涵盖安全相关任务&#xff08;如有害内容检测、隐私保护、道德推理等&#xff09;。 1.1 数据收集 描…...

Qt 事件处理中 return 的深入解析

Qt 事件处理中 return 的深入解析 在 Qt 事件处理中&#xff0c;return 语句的使用是另一个关键概念&#xff0c;它与 event->accept()/event->ignore() 密切相关但作用不同。让我们详细分析一下它们之间的关系和工作原理。 核心区别&#xff1a;不同层级的事件处理 方…...

Sklearn 机器学习 缺失值处理 获取填充失值的统计值

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 使用 Scikit-learn 处理缺失值并提取填充统计信息的完整指南 在机器学习项目中,数据清…...