• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            SRM 144 DIV 2 1100

            Problem Statement

                

            You work for an electric company, and the power goes out in a rather large apartment complex with a lot of irate tenants. You isolate the problem to a network of sewers underneath the complex with a step-up transformer at every junction in the maze of ducts. Before the power can be restored, every transformer must be checked for proper operation and fixed if necessary. To make things worse, the sewer ducts are arranged as a tree with the root of the tree at the entrance to the network of sewers. This means that in order to get from one transformer to the next, there will be a lot of backtracking through the long and claustrophobic ducts because there are no shortcuts between junctions. Furthermore, it's a Sunday; you only have one available technician on duty to search the sewer network for the bad transformers. Your supervisor wants to know how quickly you can get the power back on; he's so impatient that he wants the power back on the moment the technician okays the last transformer, without even waiting for the technician to exit the sewers first.

            You will be given three vector <int>'s: fromJunction , toJunction, and ductLength that represents each sewer duct. Duct i starts at junction (fromJunction[i] ) and leads to junction (toJunction[i]). ductlength[i] represents the amount of minutes it takes for the technician to traverse the duct connecting fromJunction[i] and toJunction[i]. Consider the amount of time it takes for your technician to check/repair the transformer to be instantaneous. Your technician will start at junction 0 which is the root of the sewer system. Your goal is to calculate the minimum number of minutes it will take for your technician to check all of the transformers. You will return an int that represents this minimum number of minutes.

            Definition

                
            Class: PowerOutage
            Method: estimateTimeOut
            Parameters: vector <int>, vector <int>, vector <int>
            Returns: int
            Method signature: int estimateTimeOut(vector <int> fromJunction, vector <int> toJunction, vector <int> ductLength)
            (be sure your method is public)

                題目意思:圖中有n個(gè)點(diǎn),從邊(u,v)的權(quán)值是點(diǎn)u到點(diǎn)v所需的時(shí)間。現(xiàn)在需要遍歷圖中所有的點(diǎn),問(wèn)所需要的最少時(shí)間是多少。
                這類題目有一種一般的做法:設(shè)ans=2*∑cost(u,v),為所有邊的權(quán)值的和的2倍;再?gòu)钠瘘c(diǎn)s找一條簡(jiǎn)單路徑path,滿足:path上的所有權(quán)值之和最大;這個(gè)可以用一個(gè)簡(jiǎn)單的dfs輕松搞定;最后ans-path就是所需的最短時(shí)間。
            #include <iostream>
            #include 
            <vector>
            #include 
            <algorithm>
            using namespace std;

            class PowerOutage{
            public:
                
            int estimateTimeOut(vector<int> fromJunction, vector<int> toJunction, vector<int> ductLength);
                
            int dfs(int index, vector<int> fromJunction, vector<int> toJunction, vector<int> ductLength);
            }
            ;
            int PowerOutage::dfs(int index, vector<int> fromJunction, vector<int> toJunction, vector<int> ductLength){
                
            int i,ans=0,len=fromJunction.size();
                
            for(i=0;i<len;i++)
                    
            if(fromJunction[i]==index)
                        ans
            =max(ans,ductLength[i]+dfs(toJunction[i],fromJunction,toJunction,ductLength));
                
            return ans;
            }

            int PowerOutage::estimateTimeOut(vector<int> fromJunction, vector<int> toJunction, vector<int> ductLength){
                
            int i,ans=0,len=ductLength.size();
                
            for(i=0;i<len;i++)
                    ans
            +=2*ductLength[i];
                ans
            -=dfs(0,fromJunction,toJunction,ductLength);
                
            return ans;
            }

            posted on 2009-05-23 14:42 極限定律 閱讀(599) 評(píng)論(0)  編輯 收藏 引用 所屬分類: TopCoder


            只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
            相關(guān)文章:
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問(wèn)   Chat2DB   管理


            <2009年4月>
            2930311234
            567891011
            12131415161718
            19202122232425
            262728293012
            3456789

            導(dǎo)航

            統(tǒng)計(jì)

            常用鏈接

            留言簿(10)

            隨筆分類

            隨筆檔案

            友情鏈接

            搜索

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            久久精品国产亚洲AV影院| 久久青青草原亚洲av无码| 狠狠色婷婷久久一区二区| 一本久道久久综合狠狠爱| 国内精品人妻无码久久久影院| 国产成人久久精品一区二区三区 | 狠狠色丁香久久婷婷综合| 精品久久久久久国产91| 免费一级欧美大片久久网| 日韩人妻无码精品久久免费一 | 久久www免费人成精品香蕉| 日本人妻丰满熟妇久久久久久| 久久精品一区二区| 亚洲精品国产字幕久久不卡| 国产精品伊人久久伊人电影 | 久久婷婷国产麻豆91天堂| 狠狠色丁香久久婷婷综合蜜芽五月| 国内精品久久久久影院一蜜桃| 亚洲&#228;v永久无码精品天堂久久 | 久久久久一本毛久久久| 久久亚洲AV无码精品色午夜麻豆| 国产精品激情综合久久| 国产午夜免费高清久久影院| 精品人妻伦九区久久AAA片69| 人人狠狠综合久久亚洲| 久久久久久久久久免免费精品| 69久久精品无码一区二区| 日本久久久久亚洲中字幕| 欧美伊人久久大香线蕉综合| 色99久久久久高潮综合影院 | 久久综合给合久久狠狠狠97色69| 亚洲国产精品综合久久网络 | 2021少妇久久久久久久久久| 亚洲第一极品精品无码久久| 久久天天躁狠狠躁夜夜2020一| 一级a性色生活片久久无少妇一级婬片免费放 | 东方aⅴ免费观看久久av| 香蕉久久夜色精品国产尤物| 大香伊人久久精品一区二区| 日产精品久久久久久久| 亚洲精品乱码久久久久66|