Chrety

分类

C++(8) DOS(2) Python(2) 动态规划(12) 图论(8) 字符串(1) 学习笔记(10) 数学(10) 数据结构(14) 未归档(2) 杂(1) 算法(13) 详尽的思路(1) 题解(1)

/ 注册

全部文章（共4篇）

loj#10067 构造完全图(最小生成树)

题目 loj#10067 构造完全图解析和kruscal类似，我们要构造一个完全图，考虑往这颗最小生成树里加边我们先把每一条边存下来，把两个端点分别放在不同的集合内，记录每个集合的大小，然后做kruscal，集合之间两两构造完全图，即两两合并，直到合并成为一个集合。因为本来就有一条边...

图论 kruscal 最小生成树

2019-07-21

0 622

BZOJ1003: [ZJOI2006]物流运输(最短路+DP)

题目： 1003: [ZJOI2006]物流运输解析：最短路+DP 我们用\(no[i][j]\)来表示\(i\)在第\(j\)天不可以经过用\(cost[i][j]\)表示第\(i\)天到第\(j\)天的花费在最短路的时候判断一下在第\(i\)天到第\(j\)天中哪些码头不可以走，在...

图论 DP 最短路

2019-08-13

0 565

BZOJ1040: [ZJOI2008]骑士(奇环树,DP)

题目： 1040: [ZJOI2008]骑士解析：假设骑士\(u\)讨厌骑士\(v\)，我们在\(u\)，\(v\)之间连一条边，这样我们就得到了一个奇环树（奇环森林），既然是一颗奇环树，我们就先考虑把环断开，设断开边边连接的两点是\(rt1\)，\(rt2\)，断环的话直接标记这条边不能...

DP 图论奇环树

2019-08-15

0 494

loj#10078. 新年好(最短路)

题目： loj#10078. 新年好解析：亲戚只有五个，可以把它们看成2,3,4,5,6号点，分别跑最短路，记录一下距离，然后DFS一下这题非常玄学，我开了一个\(12*12\)的数组，没有离散化，竟然过了，开到\(5050*5050\)就RE，玄学代码： #include <...

图论最短路

2019-08-31

0 485