HIT-软件构造 | Lab1 项目配置
HIT 软件构造课程实验 Lab1 项目配置说明
【阅读笔记】深入理解计算机系统
This book (CS:APP3e) is the third edition of a book that stems from the introductory computer systems course we developed at Carnegie Mellon University, starting in the Fall of 1998, called "Introduction to Computer Systems" (ICS).
【课程笔记】Udemy - The Complete JavaScript Course 2022: From Zero to Expert!
The modern JavaScript course for everyone! Master JavaScript with projects, challenges and theory. Many courses in one!
【课程笔记】Udemy - Advanced CSS and Sass: Flexbox, Grid, Animations and More!
The most advanced and modern CSS course on the internet: master flexbox, CSS Grid, responsive design, and so much more.
【课程笔记】Udemy - Build Responsive Real-World Websites with HTML and CSS
Learn modern HTML5, CSS3 and web design by building a stunning website for your portfolio! Includes flexbox and CSS Grid
Bullet Journal | 子弹笔记 | 2022
VonBrank的2022年度子弹笔记
【OI考古】图论 | 拓扑排序
对于一个有向无环图(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] ,非 ...
【OI考古】图论 | 最小生成树
最小生成树(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 2 ...
【OI考古】图论 | 二分图匹配
先决条件
二分图
二分图的匹配
增广路
对于一个二分图 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,vnu 的匹配,其余匹配不变,所得的图 GGG 的新匹配 M′M'M′ 匹配数必大于 MMM 。重复寻找这样的增广路,经过有限次操作后,必能最大化 MMM 的匹配数。
模板题 - 洛谷 P3386 | 【模板】二分图最大匹配
题目描述
题目描述
给定一个二分图,其左部点的个数为 nnn ,右部点的个数为 mmm ,边数为 eee ,求其最大匹配的边数。
左部点从 111 至 nnn 编号,右部点从 111 至 mmm 编号。
输入格式
输入的第一行是三个整数,分别代表 n,mn,mn,m 和 eee 。
接下来 eee 行,每行两个整数 u,vu, vu,v ,表示 ...
【OI考古】图论 | 割点和桥
割点
对于一个无向图 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
输出
1215
说明/提示
对于全部数据, 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 算法的基本实现 ...