TsReaper's Blog

我的新博客：http://tsreaper.com，大家都去新博客吧～

关键字：差分约束。

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。他们之间的关系自然也极不和谐。