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

Re:雁过留声——分治与dfs

Posted by hbl at 2010-03-19 18:56:11 on Problem 3222
In Reply To:雁过留声——分治与dfs Posted by:fanhqme at 2009-09-26 17:57:30
有个错误:
        否则若px不是-1
              px=y
应改为:若px是-1,px=y


> 其实,如果仔细深究,就会发现:dfs本身也是分治!
> 看一下搜索树的产生过程:
> 随便选一个根,依次找把它剔除后产生的破碎的联通块,
> 再依次产生搜索子树。
> 
> 对于这种匹配的题,往往有两个思路:二分匹配或分治
> 二分匹配就是把题目套上现成的匹配模型,
> 往往需要找到一种巧妙的染色方法以形成“二分”的图。
> 分治,则是通过这样的一种思想:
> 随便选一个节点或一条边,
> 把图断开,递归解决子图,然后通过这个点或边“调剂”一下,
> 许多图上找回路、找割定的问题都是用这个思想。
> 
> 看一下这个题吧:
> 二分匹配似乎没戏了,那就分治。
> 断开一个点x,然后看分离出的子图。
> 对于每一个子图,需要大胆的不妨设只会有两种情况:
> 1.子图内部匹配成功。
> 2.子图内部无法匹配,富裕出一条连着x的某个邻居y的边(y,w)。
> 
> 这个其实是需要证明的,不过,以下的算法就是证明:
> 对于情况1,把x与那个子图的所有连边统统划归x的“待匹配边表”
> 对于情况2,把(x,y)这个边“赠送”给那个子图,使得它可以匹配,
> 剩下的边归入“待匹配边表”
> 最后,把x的“待匹配边表”中的所有边两两匹配一下,
> 再看一下是否可以匹配或富裕一条边。
> 
> 具体写的时候,可以用dfs巧妙地实现,dfs伪代码如下:
> dfs u
>    记录u的时间戳
>    px=-1//记录用于“调剂”的那个边
>    对于u的每一个邻居y
>       如果y还没有访问,dfs y,
>           如果返回多余一条边(y,w),则输出(u,y) (y,w)
>           否则若px不是-1
>               px=y
>           否则输出(px,u) (u,y)并px=-1
>       如果y访问过,但是它的时间戳比u晚,则
>           若px不是-1
>               px=y
>           否则输出(px,u) (u,y)并px=-1
>     最后返回px

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