henry_y

分类

A-学习笔记(10) A-游记/杂谈(2) B-题库-51nod(2) B-题库-AtCoder(7) B-题库-BZOJ(48) B-题库-CodeForces(5) B-题库-HDU(5) B-题库-LibreOJ(7) B-题库-Luogu(16) B-题库-POJ(1) B-题库-牛客网(8) C-博客园美化(1) C-比赛记录及刷题计划(2) 动态规划-DP(12) 图论-网络流(1) 图论·最短路(3) 字符串-hash(1) 字符串-KMP(1) 字符串-Trie(2) 思想-分块(4) 思想-前缀和(1) 数据结构及算法-单调队列(4) 数据结构及算法-堆(2) 数据结构及算法-树链剖分(2) 数论-其他(3) 数论-博弈论(1) 数论-数论分块(1) 数论-欧拉函数(1) 数论-莫比乌斯反演(1) 数论·筛法(4) 未归档(3) 深度优先搜索-dfs(1) 贪心(1) 题解(37)

/ 注册

全部文章（共3篇）

题解 | relays 题解

考虑先离散化，那么点的个数只会有个最多。于是复杂度里面就可以有一个.考虑构造矩阵表示经过一条边的最短路，那么就会是输入进来的边。那么表示经过条边的最短路，则有;然后就可以处理出次方的所有矩阵，然后得到最终矩阵的答案了。这个算法叫做倍增floyd #include <cstdio> #i...

矩阵快速幂 floyd

2019-09-02

0 588

[luoguP1119]灾后重建

题目链接毒瘤题卡spfa 可能dij也卡，没试过然后放floyd过了但其实spfa很好打，虽然只有60 让我们来分析一下spfa的效率，假设这个出题人极其毒瘤，出网格图又因为是在线询问，所以对于每次询问都得跑一次spfa 所以效率上界为$O(n*m*Q)$ 代入一下最坏...

floyd

2018-07-24

0 501

[bzoj 1774][Usaco2009 Dec]Toll 过路费

题目描述跟所有人一样，农夫约翰以着宁教我负天下牛，休叫天下牛负我的伟大精神，日日夜夜苦思生财之道。为了发财，他设置了一系列的规章制度，使得任何一只奶牛在农场中的道路行走，都要向农夫约翰上交过路费。农场中由N（1 <= N <= 250）片草地（标号为1到N），并且有M（1 &l...

floyd 最短路

2018-08-16

0 587