• <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個點(diǎn),從邊(u,v)的權(quán)值是點(diǎn)u到點(diǎn)v所需的時間。現(xiàn)在需要遍歷圖中所有的點(diǎn),問所需要的最少時間是多少。
                這類題目有一種一般的做法:設(shè)ans=2*∑cost(u,v),為所有邊的權(quán)值的和的2倍;再從起點(diǎn)s找一條簡單路徑path,滿足:path上的所有權(quán)值之和最大;這個可以用一個簡單的dfs輕松搞定;最后ans-path就是所需的最短時間。
            #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 極限定律 閱讀(600) 評論(0)  編輯 收藏 引用 所屬分類: TopCoder


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


            <2009年5月>
            262728293012
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456

            導(dǎo)航

            統(tǒng)計

            常用鏈接

            留言簿(10)

            隨筆分類

            隨筆檔案

            友情鏈接

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久国产成人午夜AV影院| 久久免费看黄a级毛片| AAA级久久久精品无码片| 久久99精品国产麻豆| 国产精品久久成人影院| 91久久精品国产91性色也| 亚洲国产综合久久天堂| 久久亚洲私人国产精品| 国产精品久久久久乳精品爆| 久久只有这里有精品4| 久久精品国产69国产精品亚洲| 日韩亚洲国产综合久久久| 亚洲成色www久久网站夜月| 精品99久久aaa一级毛片| 久久99精品久久久久久久不卡 | 国产69精品久久久久9999APGF | 久久这里只有精品视频99| 亚洲午夜久久久久妓女影院| 国产精品伊人久久伊人电影| 无码人妻精品一区二区三区久久久 | 天天久久狠狠色综合| 青青草原综合久久大伊人| 久久国产精品-久久精品| 99久久无色码中文字幕人妻| 精品久久人人做人人爽综合| 丰满少妇人妻久久久久久| 久久久久亚洲av综合波多野结衣| 久久精品国产亚洲Aⅴ蜜臀色欲| 国产精品久久久久AV福利动漫| 思思久久精品在热线热| 久久伊人亚洲AV无码网站| 精品水蜜桃久久久久久久| 国产高清美女一级a毛片久久w| 7777久久亚洲中文字幕| 精品久久香蕉国产线看观看亚洲| 久久综合国产乱子伦精品免费| 亚洲乱码中文字幕久久孕妇黑人 | 久久精品国产精品亚洲| 久久婷婷人人澡人人| 久久久久亚洲AV成人网人人软件| 久久久精品国产亚洲成人满18免费网站 |