wxyww

分类

未归档(12) 精品(28) 题解(65)

/ 注册

全部文章（共5篇）

灌溉

灌溉【问题描述】 Farmer John 有𝑛个牧场，他希望灌溉他的所有牧场。牧场编号为1 ∼ 𝑛，要灌溉一个牧场有两种方式，一个是直接在这个牧场建设一个小型水库，另一个是从别的牧场向这个牧场引水。在第𝑖个牧场建立小型水库需要𝑊%美元，而从第𝑖 个牧场向第?...

最小生成树

2018-05-01

0 0

[luogu1967][货车运输]

题目链接题意：其实题目的意思就是问从x到y权值最小的路的权值最大能是多少。思路：首先可以先把这张图变成一棵树。因为那些更小的点肯定是不跑更优秀，而且题目没有要求路程，所以生成一棵树，只要能保证在同一个图里面的点能够连通即可。又因为他要使最小权值最大，所以可以只留下那些权值更大的边。所...

最近公共祖先最小生成树

2018-08-21

0 378

UOJ176 新年的繁荣

题目链接 Boruvka生成树算法 \(Boruvka\)算法就是先把每个点看作一个联通块，然后不断在联通块之间找最优的边进行合并。因为每次联通块的数量最少缩小一半。所以合并次数是\(log\)的先把所有的点权挂到\(trie\)树上。然后对于每个联通块进行合并的时候。对于联通块中的每个点都去...

最小生成树

2019-01-21

0 639

灌溉

灌溉【问题描述】 Farmer John 有𝑛个牧场，他希望灌溉他的所有牧场。牧场编号为1 ∼ 𝑛，要灌溉一个牧场有两种方式，一个是直接在这个牧场建设一个小型水库，另一个是从别的牧场向这个牧场引水。在第𝑖个牧场建立小型水库需要𝑊%美元，而从第𝑖 个牧场向第?...

最小生成树

2018-05-01

0 455

[luogu1967][货车运输]

题目链接题意：其实题目的意思就是问从x到y权值最小的路的权值最大能是多少。思路：首先可以先把这张图变成一棵树。因为那些更小的点肯定是不跑更优秀，而且题目没有要求路程，所以生成一棵树，只要能保证在同一个图里面的点能够连通即可。又因为他要使最小权值最大，所以可以只留下那些权值更大的边。所...

最近公共祖先最小生成树

2018-08-21

0 467