ThinkofBlank

论文

未归档(4) 题单(1) 题解(90)

/ 注册

全部文章 / 论文（共3篇）

关于无向图缩点

把之前的补过来/xk 最近,做了好多图论,其中大部分都跟tarjan有关,而又有好多无向图。。。orz 我们都知道,tarjan会把能互达的若干点合并为一个点,然而,在无向图中,所有点都可互达(图联通),故,整个图就会缩成一个点...然鹅,我们把图画出来,又是另外的样子...明明就只有一个环,却把所...

理解图论研究

2020-05-19

0 1624

关于扩展欧几里得中求最小非负x的方法的推导

推导假设,我们已经求出有一对x,y满足ax+by=gcd(a,b)。我们想要求最小非负整的x,那么必须要减去一个能减的最大值,我们设减去一个D,则方程变为: a(x-D)+by+aD=gcd(a,b) 整合一下： a(x-D)+b(y-aD/b)=gcd(a,b) 我们...

数论理解

2018-12-19

0 603

玄学最短路算法——Ex Floyd 来自专栏

Floyd再思考 ——by ThinkofBlank 一.序言 Floyd,是一个十分常用的图论算法，其作用是在O(n^3)的时间内计算出全源最短路。其实现原理是利用的dp,然而，刚开始接触Floyd的时候，并没有去尝试理解，思路此算法，仅仅记了下打法就跑了，最近无聊时思考了下，得...

研究优化理解图论

2019-02-24

0 765