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^3的算法超时了，用Branch&Bound又不知如何找环，郁闷...

Posted by gongml at 2005-10-27 03:59:47 on Problem 2679

Followed by:

总算挤过去了，那位高手有快一点的算法请给解释一下。 (0) gongml 2005-10-27 04:45:07
- 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