TsReaper's Blog

关键字：差分约束。

Link&Limit

[洛谷1993]  [BZOJ3436]

时间限制：1000ms  空间限制：131072kb

Description

小 K 在 Minecraft 里面建立很多很多的农场，总共 n 个，以至于他自己都忘记了每个农场中种植作物的具体数量了，他只记得一些含糊的信息（共 m 个），以下列三种形式描述...

之前学习差分约束的时候有两个问题一直没有弄明白：不等式是怎么转换为图的？以及到底要算最长路还是最短路呢？这篇心得就来解决这两个问题。并介绍常见的用于构造不等式的限定关系。

关键字：最长路。

Link&Limit

[洛谷1983]  [codevs3294]

时间限制：1000ms  空间限制：131072kb

Description

一条单向的铁路线上，依次有编号为 1, 2, …, n 的 n 个火车站。每个火车站都有一个级别，最低为 1 级。现有若干趟车次在这条线路上行驶，每一趟都满足如下要求：如果这趟车次停靠了火车站 x，则始发站、终点站之间所有级别大于等于火车站 x 的都必须停靠。

关键字：二分，图的黑白染色。

Link&Limit

[洛谷1525]  [codevs1069]

时间限制：1000ms  空间限制：131072kb

Description

S 城现有两座监[防和谐]狱，一共关押着N 名罪[防和谐]犯，编号分别为1~N。他们之间的关系自然也极不和谐。

[好题] 关键字：树的性质。

Link&Limit

[洛谷1268]

时间限制：1000ms  空间限制：131072kb

Description

树可以用来表示物种之间的进化关系。一棵“进化树”是一个带边权的树，其叶节点表示一个物种，两个叶节点之间的距离表示两个物种的差异。现在，一个重要的问题是，根据物种之间的距离，重构相应的“进化树”。