【题目大意】给出一个图，让你求出（点权/边权）最大的那个回路的（点权/边权）的值。
【算法分析】由于对于一个环，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
这段时间做了不少seach。现在来总结一下。
1、关于dfs和dfs-id。
应当考虑到的剪枝有:上界，下界，可行性剪枝，最优性剪枝。
TIPS:也许给数据排下序会有更强大的剪枝。
2、bfs
hash很重要
3、双向bfs
动态调整搜索方向很重要，即取节点少的一边去扩展。
4、A*
这个是老大，这个是重点，传说中最快的搜索。
f(s)=g(s)+h(s)——h是估价函数。
再次来重点：
估价函数h(s)的条件：1、h(s)必须是从s到达目标点的下界。2、h(s1)<=h(s2)+c[s1,s2]。c是转移代价。
然后是A*的实现：
一个堆，一个hash list（没有删除操作）。然后每次取堆顶元素（注意，堆顶元素的f值不可能再次改变）
然后扩展，如果扩展出来的节点hash list里没有，那就加入堆，否则如果扩展出来的点的F值小于堆中的，就更新堆。然后当目标节点出现在堆顶的时候，就可以输出了。因为堆顶元素的f值不可能再次改变了。
【题目大意】给出一棵树及上面节点的值，问最少改变多少个点的值能使其满足left 【算法分析】就是后序遍历这颗树，排出一个顺序，然后每个点减去一个值，然后在求最长不下降子序列就可以了。具体看dfs部分，不过不知道问什么我注释那样写是WA的。 http://acm.pku.edu.cn/JudgeOnline/showmessage?message_id=136017 按照这个的话，我觉得按我注释那样增加del应该也是对的。。。如果有知道的麻烦回复告诉我 【其它】1RE，1WA，1A 6410874 edward2 3214 Accepted 12920K 1188MS G++ 942B 2010-02-04 19:47:48 【CODE】 #include