luogu3420(POI)

发表于 2017-10-10 | 分类于 luogu

POI中的大大大水题，做法很多，最最麻烦的可以tarjan缩点之后判断有多少入度为0的点，简单的话可以直接深搜，反正我是随手敲了一个并查集，因为错误的数据范围WA了一次然后1A。

poj3683

发表于 2017-10-10 | 分类于 poj

昨天做这道题的时候各种错误，今天早上终于调好了。

发表于 2017-10-10 | 分类于 poj

一道对于最小生成树算法的很不错的应用。

题目要求是给你一张图，求一棵树，要求其 最大边与最小边的差值 最小。

发表于 2017-10-09 | 分类于 bzoj

应该是改编自USACO的田忌赛马？最好的情况好处理，直接套用田忌赛马思想，排序后从小的开始比较，可以比过就加分，

发表于 2017-10-08 | 分类于 poj

有n个任务，给出任务时间和起点终点，每两个点之间的时间花费为其曼哈顿距离，问若要每个任务都按时开始需要多少出租车。

发表于 2017-10-08 | 分类于 poj

一道很经典的题，因为一块儿泥地可以被横着的木板覆盖也可以被竖着的木板覆盖，所以对于每个联通块我们横纵坐标分别标号，然后连接对应的横纵标号建图，求一遍最小覆盖即可。

发表于 2017-09-21 | 分类于 poj

两道入门的2-sat，只要判定是否有解即可。

发表于 2017-09-21 | 分类于 poj

poj六道2-sat中的最后一道。事实上也算比较基础的，不用输出方案，只是建图的时候要多注意一些。

大意是给你两个源点，有n个点要向这两个点中的一个连边，边长为他们的曼哈顿距离，其中有的点必须连同一个源点，有的点必须连不同的源点。两个源点之间有边。给出两个源点和这n个点的坐标，要求使这n个点中任意两点之间的边长（点到源点再到点的边长）尽可能的小。

发表于 2017-09-21 | 分类于 poj

一道很基础的2-sat，题目链接戳这里。

大意是，你有n对钥匙，每对钥匙中只能选一个。你要开m个门，每个门可以用两把给定钥匙中的任意一把打开，问你最多能开到第几道门。

发表于 2017-09-20 | 分类于 bzoj

本来是打算这两天一口气刷完poj的6到2-sat的，但昨天的模拟赛被一道题高斯消元直接虐了3个半小时没调出来，后来发现自己的高斯消元的板子就是错的= =。。