posts - 403, comments - 310, trackbacks - 0, articles - 7
            BlogJava :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理

          TopCoder SRM 144 - PowerOutage

          Posted on 2007-08-14 17:12 ZelluX 閱讀(484) 評論(0)  編輯  收藏 所屬分類: Algorithm
          一開始沒看清題目,以為是在網狀圖中找遍歷所有點的最短路徑
          后來才發現是在一棵樹中,而且是從根節點出發,這個就簡單多了
          把所有路徑加起來乘以2,就是從根節點到各個路徑后再返回根節點所需的最短耗費。
          然后再減掉訪問最后一個節點后返回所需的耗費即可,既然要求最小的耗費就減去耗費最大的路徑即可。

          public class PowerOutage {
              
          public static int estimateTimeOut(int[] fromJunction, int[] toJunction, int[] ductLength) {
                  
          int sum = 0;

                  
          for (int i = 0; i < ductLength.length; i++)
                      sum 
          += ductLength[i];
                  
                  sum 
          *= 2;
                  sum 
          -= findLongestWay(0, fromJunction, toJunction, ductLength);
                  
          return sum;
              }

              
          public static int findLongestWay(int root, int[] fromJunction,
                      
          int[] toJunction, int[] ductLength) {
                  
          int max = 0;

                  
          for (int i = 0; i < fromJunction.length; i++) {
                      
          if (fromJunction[i] == root) {
                          
          int temp = findLongestWay(toJunction[i], fromJunction,
                                       toJunction, ductLength) 
          + ductLength[i];
                          
          if (temp > max)
                              max 
          = temp;
                      }
                  }

                  
          return max;
              }
          }


          主站蜘蛛池模板: 新建县| 双鸭山市| 芒康县| 峡江县| 密山市| 贺兰县| 阿克苏市| 思南县| 公主岭市| 正宁县| 上犹县| 禄劝| 唐河县| 金堂县| 南宁市| 临桂县| 黄冈市| 温州市| 马鞍山市| 砀山县| 辽阳县| 体育| 息烽县| 阳山县| 泰州市| 云龙县| 太和县| 承德市| 雷山县| 安阳县| 天台县| 泸水县| 永康市| 色达县| 韶山市| 双柏县| 卓尼县| 枞阳县| 虞城县| 深圳市| 凤山县|