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:终于过了,讲下算法.

Posted by zzsx65zdf at 2011-10-21 00:07:32 on Problem 1486
In Reply To:终于过了,讲下算法. Posted by:alpc07 at 2007-10-08 20:48:41
其实不要删除后再求匹配数是否减少的
只要枚举每条匹配边
(l,r);
删除这条边; 删除这个匹配link[r]:=0;
再从l找增广路
找到则(l,r)不是必须边
否则就输出这条边
注意恢复只要把link[r]改回:=l;就行了,重新找增广路的时候不改变图。

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