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

关于网上解题报告两个问题的补充

Posted by s13a_qw4990 at 2014-01-10 15:45:10 on Problem 3621
一:
  网上很多解题报告都是构图后直接取一个点作为起点,然后SPFA判断,这个是有问题的,比如有3个点,
分别2->1 2->3 3->2,如果直接把1当作起点,就会判断出无环,但存在一个2->3 3->2的环。

二:
  网上的构图都是把新的边权赋值为 f-ans*t ,ans是猜测的答案,t是从u到v的时间,f是v点的fun值。
  但是由于一个点可能被经过多次,但其fun值却只算一次,如果这样构图的话,是会把多次经过点的fun值计算多次的,这里看似会有点问题。
  不过比较凑巧的是最优的环,是不会包含一个点被经过多次的情况的(证明见下),所以这样构图过后也能求出正确答案。

  关于上面那个结论的简单证明:
    首先如果一个点被经过多次,那么他一定是几个环的公共交点,现在假设他是2个环的交点,并且他本身的fun值为f,假设环1的总fun值为F1,总时间为T1,环2的为F2和T2,并且假设环1优于环2,即是有F1/T1 > F2/T2 ,那么只需要证明在此假设下 (F1+F2-f)/(T1+T2) < F1/T1 就行了,后略。 

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