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
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

hoho,终于淌过了,很暴力的增广路

Posted by zeroh323 at 2008-08-31 10:26:56 on Problem 3189
我的做法是:
  设两个指针:head, tail。从1 到 B 线性扫过去,每次做一次网络流,看是否流为N,
  复杂度是B*XXX, 其中XXX代表增广路的复杂度喇。呵呵。。
  不过这样做是会超时,加了一个优化:当head右移的时候,需要重新做网络流,而当tail右移
  的时候,只需要在原来流的基础上加边,继续增广就行了。加了这也优化后,我的是500+ms,
  还是很囧,不过总算趟过去了。呵呵。

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