Von Brank

哈尔滨工业大学夏季学期「基于Java EE平台的软件开发（田英鑫老师）」课程笔记

对于一个有向无环图（DAG），我们要找出一种顶点的排序方式，使得对于图中任意 u,vu, vu,v ，如果 u,vu, vu,v 之间有一条 uuu 指向 vvv 的有向路，则 uuu 排在 vvv 的前面。这种排序方式被称为拓扑排序（Topological sorting）。 下图是一个DAG： 2,1,3,5,4,62, 1, 3, 5, 4, 62,1,3,5,4,6 是其一个拓扑排序。 模板题 题目 P1038 [NOIP2003 提高组] 神经网络 背景 人工神经网络（Artificial Neural Network）是一种新兴的具有自我学习能力的计算系统，在模式识别、函数逼近及贷款风险评估等诸多领域有广泛的应用。对神经网络的研究一直是当今的热门方向，兰兰同学在自学了一本神经网络的入门书籍后，提出了一个简化模型，他希望你能帮助他用程序检验这个神经网络模型的实用性。 题目描述 在兰兰的模型中，神经网络就是一张有向图，图中的节点称为神经元，而且两个神经元之间至多有一条边相连，下图是一个神经元的例子： 每条边有一个权值，输入点有一个初始权值 C[i]C[i]C[i] ，非输 ...

最小生成树（MST），顾名思义，对于带权无向连通图 GGG ，其所有生成树中的权值和最小者 TTT ，是其最小生成树。 模板题 题目 洛谷 P3366 | 【模板】最小生成树 题目描述 如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。 输入格式 第一行包含两个整数 N,MN,MN,M ，表示该图共有 NNN 个结点和 MMM 条无向边。 接下来 MMM 行每行包含三个整数 Xi,Yi,ZiX_i,Y_i,Z_iXi​,Yi​,Zi​​ ，表示有一条长度为 ZiZ_iZi​​ 的无向边连接结点 Xi,YiX_i,Y_iXi​,Yi​ ​ 。 输出格式 如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz 。 输入输出样例 输入 1234564 51 2 21 3 21 4 32 3 43 4 3 输出 17 说明/提示 数据规模： 对于 20%20\%20% 的数据， N≤5N\le 5N≤5 ， M≤20M\le 20M≤20 。 对于 40%40\%40% 的数据， N≤50N\le 50N≤50 ， M≤2500M\le ...

先决条件 二分图 二分图的匹配 增广路 对于一个二分图 GGG ，对于一个匹配 MMM ，若 ∃ u,v∉M\exist \ u, v \notin M∃ u,v∈/M ，则 u,vu, vu,v 间任意路 u,v1,v2,…,vn,vu, v_1, v_2, \dots , v_n , vu,v1​,v2​,…,vn​,v 是一条增广路。 显然，在该增广路上构造包含 uv1,vnuuv_1, v_nuuv1​,vn​u 的匹配，其余匹配不变，所得的图 GGG 的新匹配 M′M'M′ 匹配数必大于 MMM 。重复寻找这样的增广路，经过有限次操作后，必能最大化 MMM 的匹配数。 模板题 - 洛谷 P3386 | 【模板】二分图最大匹配 题目描述 题目描述 给定一个二分图，其左部点的个数为 nnn ，右部点的个数为 mmm ，边数为 eee ，求其最大匹配的边数。 左部点从 111 至 nnn 编号，右部点从 111 至 mmm 编号。 输入格式 输入的第一行是三个整数，分别代表 n，mn，mn，m 和 eee 。 接下来 eee 行，每行两个整数 u,vu, vu,v ，表示 ...

割点 对于一个无向图 GGG ，如果把一个点 uuu 删除后这个图的极大连通分量数增加了，那么这个点就是这个图的割点（又称割顶）。 模板题： 洛谷 P3388 - [模板]割点(割顶) 题目描述 给出一个 nnn 个点， mmm 条边的无向图，求图的割点。 输入格式 第一行输入两个正整数 n,mn,mn,m 。 下面 mmm 行每行输入两个正整数 x,yx,yx,y 表示 xxx 到 yyy 有一条边。 输出格式 第一行输出割点个数。 第二行按照节点编号从小到大输出节点，用空格隔开。 输入输出样例 输入 123456786 71 21 31 42 53 54 55 6 输出 121 5 说明/提示 对于全部数据， 1≤n≤2×1041\leq n \le 2\times 10^41≤n≤2×104 ， 1≤m≤1×1051\leq m \le 1 \times 10^51≤m≤1×105 。 点的编号均大于 000 小于等于 nnn 。 tarjan图不一定联通。 Tarjan算法求割点 解决这类连通性相关的图论问题通常都要请出Tarjan算法。关于Tarjan算法的基本实现思路可以参 ...

简介 强连通分量（Strongly Connected Components）指有向图 GGG 中的极大子图，其满足子图内所有顶点都可以互相到达。 强连通分量是有向图 GGG 上的一种等价关系，每个SCC可以缩成一个点，便于后续的处理。 顺便吐槽一下最近在学校学的图论：把“连通分量”称为“连通分支”我忍了，把“二分图”称为“偶图”我也忍了，把“二叉树”叫“二元树”是什么鬼。虽然在图论学界术语不统一的背景下，对对象的称呼仅仅是习惯问题，但血压依然上来了（（ 模板题 | P3916 | 图的遍历 题目描述 给出 NNN 个点， MMM 条边的有向图，对于每个点 vvv ，求 A(v)A(v)A(v) 表示从点 vvv 出发，能到达的编号最大的点。 输入格式 第 111 行， 222 个整数 NNN , MMM 。 接下来 MMM 行，每行 222 个整数 UiU_iUi​ , ViV_iVi​ ，表示边 (Ui,Vi)(U_i,V_i)(Ui​,Vi​) 。点用 1,2,⋯ ,N1, 2, \cdots , N1,2,⋯,N 编号。 输出格式 NNN 个整数 A(1),A(2),⋯ ,A( ...

高精度计算（Arbitrary-Precision Arithmetic），也被称作大整数（bignum）计算，运用了一些算法结构来支持更大整数间的运算（数字大小超过语言内建整型）。 先决条件 快读 C++重载运算符 高精度算法 模板题：洛谷 P1932 | A+B A-B A*B A/B A%B Problem 求 A、BA、BA、B 的和差积商余！ 题目描述 两个数两行 A BA \ BA B 输入格式 五个数 和 差 积 商 余 输出格式 输入输出样例 输入 1211 输出 1234520110 说明/提示 leng(A),leng(B)<=104leng(A),leng(B)<=10^4leng(A),leng(B)<=104 A,B>0A,B>0A,B>0 每个点 3s3s3s。 解决方案 原理 用数组模拟高精度类型，如1024可以表示成： 123456789索引：+---+---+---+---+---+| 0 | 1 | 2 | 3 | 4 |+---+---+---+---+---+内容：+---+---+---+---+---+| ...

蓝桥杯2021省赛游记

VonBrank的2021年度子弹笔记

哈工大-离散数学引论-课程笔记