Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator