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

总算挤过去了，那位高手有快一点的算法请给解释一下。

Posted by gongml at 2005-10-27 04:45:07 on Problem 2679
In Reply To:如何快速的找的环啊？用邻接矩阵n^3的算法超时了，用Branch&Bound又不知如何找环，郁闷... Posted by:gongml at 2005-10-27 03:59:47

Followed by:

n^2的吧……边数是O(n)级的…… (0) frkstyc 2005-10-27 09:52:26
- 一开始倒是删了些边，可后来用邻接矩阵找任意两点间路径还是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