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 |
关于网上解题报告两个问题的补充一: 网上很多解题报告都是构图后直接取一个点作为起点,然后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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator