Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

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:

orz...超时了... 求再优化？ (7) vrqq 2010-05-24 00:30:29
- Re:orz...超时了... 求再优化？ (35) applepi 2010-09-22 21:08:15

Post your reply here:

Home Page Go Back To top