[POJ 3621]01分数规划、spfa判正权环

【题目大意】给出一个图,让你求出(点权/边权)最大的那个回路的(点权/边权)的值。

【算法分析】由于对于一个环,V=E。所以我们可以把点权赋到以这个点为起点的边上去。这样我们就可以认为点和边是一一对应的。于是他们对应的向量x也是一样的。

然后

ans=Vx/Ex

0=Vx/Ex -ans

0=(Vx-ans*Ex)/Ex

然后构造函数f(ans)=Vx-ans*Ex                     

(∵Ex>0   ∴Vx-ans*Ex=0与(Vx-ans*Ex)/Ex=0等价,且两者关于ans的单调性一致)

然后可以发现该函数关于ans递减。

然后利用二分枚举ans,再加spfa判图中是否还有正权环就可以了。

【其它】贡献3WA。。。ORZ,可恶的精度。

6411503 edward2 3621 Accepted 360K 672MS C++ 1573B 2010-02-04 22:02:39

【CODE】

#include

加入对话

2条评论

  1. 对题意有点纠结:1、 出发点是任意的?2、 可以证明最后是一个环上存在最优解吗?重复走不会产生最优解吗?3、 从出发点找环,环一定包括出发点吗?请教博主。 

  2. 回复一毛Lionel:1对2ending back at their starting landmark    &&   the landmarks are only fun the first time they are visited  如果你走了重复说明你走了一个子环。这时候你将走了这个子环的其中一边的两遍。这个显然不会更优的。3我的出发点是所有点。参见spfa第一步

留下评论

您的电子邮箱地址不会被公开。