BZOJ 3436 小 K 的农场

发布于 2017-06-16  164 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3436

题意:问给出的差分约束系统是否存在一组可行解...


挺有意思的一道题,首先由于是求可行解,最短路还是最长路模型都没区别,于是粘了个上一题的板子...WA

为什么会 WA 呢,想到需要将每个连通块都跑一次,于是改掉,跑了 6000+ms.... 跑的很慢,做法不是很优雅...

于是考虑到这道题只需要求是否存在可行解即可,相比于传统 bfs 的 spfa 需要入队 n 次才能判断,dfs 的 spfa 只需要重复入队即存在负环了,这样跑了 36ms.... 给出两种版本的代码:

BFS:

DFS:

 

 


一个非常弱的准退役OIER