For-Mylady 2010-09-23 08:02:00
点我顶贴
收藏
删除
这四道题都是比较基础的题，很适于熟练代码。
192 ----- 赤裸裸的二分图匹配，令我很郁闷的是始终有一个点无输出，令我更郁闷的是数据很bug。
193 ----- 最小生成树，用的是并查集优化的kruskal
194 ----- 本来以为rq上没有网络流的题目，这道题是我碰见的第一个，很基础的最大流，用ford-fulkson。（p.s 向唐xx 大牛致敬，他教我的网络流）
195 ----- 广搜就完了。
一个月没上rq的题目爆炸似的增长，不错，keep going!
#1 wish@2008-05-10 02:49:00
1485
回复
删除
194 ----- 本来以为rq上没有网络流的题目，这道题是我碰见的第一个，很基础的最大流，用ford-fulkson。（p.s 向唐xx 大牛致敬，他教我的网络流）
77 恐怖分子就是最大流额 -_-
ford-fulkson 复杂度是 O(n^3m)
可以用
push and relabel 提速到 O(n^2m)
和 relabel to front 提速到 O(n^2sqrt(m))
#3 libojie@2008-05-23 03:59:00
1639
回复
删除
192——数据直接输出即可……
193——Prim也可以。O(n^2)。不知是否有人用了O(n^3)的而超时？
194——基础网络流，只不过超出NOIP大纲……
195——纯粹的Floodfill。
总体看来，题目算法一眼即可看到，兑时空优化要求不多，但编程复杂度较高，对高级算法要求较高。如果手头有算法总汇之类的资料，直接抄来即可……