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

写了十个版本!!!!泪流满面!!!!点开看时间的对比

Posted by chenbwei2012 at 2014-08-17 02:26:20 on Problem 1459
因为最近一直在写邻接表,所以一开始我写了个邻接表的EK(版本1),TLE了,然后又写了个Dinic的邻接表版本(版本2),很奇怪,也TLE了,其实是因为我的是递归的Dinic,然后我写了个邻接矩阵的EK,AC了,1700+MS,然后又打了个Dinic递归版本的邻接矩阵(版本4),TLE了。我常常听人说Dinic很快,怎么这么慢,后来才知道我是用了递归版本,于是学了Dinic的非递归版本,写了邻接表(版本5),AC了,610MS,又为了对比,写了邻接矩阵版本(版本6),AC了,516MS,之后看讨论区发现SAP很快,于是学了之后写了SAP的邻接表版本(版本7),AC了,110MS,又写了ISAP的邻接表版本(版本8),AC了,157MS,为何ISAP的邻接表会比SAP的邻接表慢呢,不解。。之后写了SAP的邻接矩阵版本(版本9),AC了,125MS,最后一个版本是ISAP的邻接矩阵版本(版本10),AC了,110MS,内流满面有木有!!
不过大神们,除了最高标号,你们的30+MS和40+MS是用的哪个Dinic和ISAP版本,跪求!!!

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