ThinkofBlank

分类

未归档(4) 论文(10) 题单(1) 题解(90)

/ 注册

TA的专栏 8篇文章 0人订阅

ThinkofBlank’s

8篇文章 1209人学习

全部文章（共6篇）

关于无向图缩点

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

理解图论研究

2020-05-19

0 1620

边的染色题解

一.闲话今天这题着实有点难想啊。。。（也许我太菜了?qwq）字数警告二.题解首先，我们先考虑答案为0的情况——存在一个所以边的边权都确定的环，其中的边权异或和为1 考虑到做这个，边权未定的边并无任何影响，所以，我们先把这些边放到一边，先把边权确定的边全部连上，然后就开始做这道题了。首先，我...

图论题解研究

2020-04-22

8 1075

题解USACO14DEC Piggyback_Silver

此题其实比较水的。。。首先我们来分析题目，我们假设，贝茜和艾尔西在i点相遇后贝西开始扛艾尔西，那么代价为多少呢？显然，代价=贝茜到i点的最小代价+艾尔西到i点的最小代价+贝茜和艾尔西一起到n点的最小代价。我们分开解决，首先贝茜到i点的最小代价=走的最少步数*b，而走的步数，我...

图论题解

2018-12-24

0 547

实现非递归树链剖分来自专栏

树链剖分，是个很神奇蛇皮的算法，他巧妙的运用了与分块类似的思想，来加速整块代码。不过，对于某些毒瘤题来说，树链剖分很可能会爆栈，如：一本通:染色。不过洛谷还好，不会爆栈。。。那么这个时候，我们就需要手动模拟来实现非递归版本的树链剖分了。注意到，整块树链剖分的代码中使用了递归的地方:...

研究优化图论

2019-01-21

1 617

题解 USACO11OPEN玉米田迷宫Corn Maze

玉米田迷宫题解一.背景 x年x月x日，竞赛老师拿此题问我，然后我玄学过了，于是特来写此题。（谁说dijkstra不能过的？？）二.分析本题，我们先不考虑有传送阵的情况，发现，其实就是一个最短路(bfs)的模板题，随便弄下就能过，不过，这里多了个传送阵，于是我们就要考虑下...

题解图论研究

2019-02-19

0 604

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

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

研究优化理解图论

2019-02-24

0 785