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

n^2的吧……边数是O(n)级的……

Posted by frkstyc at 2005-10-27 09:52:26 on Problem 2679
In Reply To:总算挤过去了，那位高手有快一点的算法请给解释一下。 Posted by:gongml at 2005-10-27 04:45:07

Followed by:

一开始倒是删了些边，可后来用邻接矩阵找任意两点间路径还是n^3。感觉用不着求任意两点间路径，可是不然想不通如何找与src&dest都相连的环... (0) gongml 2005-10-27 11:24:38
- why floyd-warshall? try bellman-ford + floodfill... (0) frkstyc 2005-10-27 11:46:38
  - 题目有些不明白，是不是既要the minimal length 也是 the minimal weight，如果已经满足 minimal length, 那么就一定不会出现 unbound 了，是么？ (0) semonteer 2005-10-27 12:21:47
    - 先判连通 void ，然后bellman－ford 判负权环unbound，最后搜双关键字的最短路(如果不存在 void)？请问是这样么？ (0) semonteer 2005-10-27 12:24:06
    - 你看错了吧…… (0) frkstyc 2005-10-27 12:29:29
      - 为什么呢？大牛指点一下？ (0) semonteer 2005-10-27 12:37:22
        money is everything，只要能省钱甚至挣钱，跑腿就无所谓了 (0) frkstyc 2005-10-27 12:39:36
        谢谢大牛 (0) semonteer 2005-10-27 12:40:38
  - 多谢多谢！改过来了，这些图论的算法都忘光了，惨... (0) gongml 2005-10-27 21:48:44
  - 请问为什么还要floodfill？ (0) SherlockBourne 2008-07-23 18:04:27

Post your reply here:

Home Page Go Back To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator