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

            <2025年6月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            293012345

            導航

            統計

            常用鏈接

            留言簿(10)

            隨筆分類

            隨筆檔案

            友情鏈接

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久天天躁狠狠躁夜夜不卡| 97精品国产97久久久久久免费| 精品久久久久久国产免费了| 久久久久久a亚洲欧洲aⅴ| 久久精品国产亚洲欧美| 亚洲国产精久久久久久久| 久久成人小视频| 久久国产精品国产自线拍免费| 久久男人中文字幕资源站| 久久人人爽人人爽人人片AV高清| 久久久久久无码Av成人影院| 久久露脸国产精品| 伊人久久无码中文字幕| 久久综合九色综合精品| 久久久久久久波多野结衣高潮| 99久久国产综合精品网成人影院| 亚洲中文字幕久久精品无码喷水| 久久亚洲综合色一区二区三区| 亚洲精品视频久久久| 精品久久久久久久久中文字幕| 亚洲乱码日产精品a级毛片久久| 91精品国产综合久久精品| 大香伊人久久精品一区二区| 国产精品VIDEOSSEX久久发布| 久久久久人妻精品一区| 久久综合亚洲鲁鲁五月天| 久久精品人妻一区二区三区| 久久国产精品成人免费| 久久精品国产亚洲AV大全| 久久中文字幕精品| 日本精品久久久久久久久免费| 久久精品国产只有精品2020| 国产午夜福利精品久久2021| 亚洲欧美伊人久久综合一区二区| 亚洲午夜福利精品久久| 久久久WWW免费人成精品| 国产成人精品久久亚洲高清不卡 国产成人精品久久亚洲高清不卡 国产成人精品久久亚洲 | 久久综合九色欧美综合狠狠| 久久91精品国产91久久小草| 国产精品免费看久久久| 久久精品国产亚洲AV无码麻豆 |