Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

Re:有没有人不用二分，直接2-SAT+枚举所有点对，输出其距离中的最大值 AC的？

Posted by l546469729 at 2016-07-07 20:12:03 on Problem 2749
In Reply To:有没有人不用二分，直接2-SAT+枚举所有点对，输出其距离中的最大值 AC的？ Posted by:yume at 2014-10-06 17:48:24

> 不二分，直接根据牛的友好或者讨厌关系建图，然后2-SAT判断可行性。若可行，在根据2-SAT的结果，对牛两两求距离取其最大值输出可以么？
> 
> 我写了下二分和不用二分的两种代码，二分的a了，不用二分的无限wrong answer。自己测了几组数据，和ac的代码输出值对比都ok。。。T_T
当然不行，2-sat的结果是一个构造解，也就是说拓扑排序并不唯一，求的就是所有可能的拓扑排序的情况中距离最大值最小的解

Followed by:

Post your reply here:

Home Page Go Back To top