BZOJ 3436 小 K 的农场


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

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


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

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

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

BFS:

DFS:

 

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 3436 小 K 的农场


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , ,