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 allh123 at 2013-04-02 12:56:43 on Problem 3259
这个题是找有没有一条权值为负的回路,用SPFA是OK的,但是如果任意选择一点搜到其他点的最短时间,入队列大于n次就证明存在负权值回路这样做是不是有BUG,假如这个图不是连通的,而你从一个孤立点开始查找,这样也许会是错的吧,题目中并没有说明这图一定是连通的,是不是要我这么想 ,在现实生活中农场的各个地方一定是连通的啊。。。。。
但是我只从1开始判断,结果也是正确的,只证明测试数据弱吧
我的想法是由于虫洞只有50个,从每个虫洞的起始点开始搜,应该不会漏算答案
然后希望用邻接表存,邻接矩阵存了的话,复杂度提高了,顶点有500个,边只有2500+200条,算稀疏图了吧
如果一定要用邻接矩阵存的话,注意一下重边的情形,选择时间花费最少的应该总是正确答案

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