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)
Constraints
-
fromJunction will contain between 1 and 50 elements, inclusive.
-
toJunction will contain between 1 and 50 elements, inclusive.
-
ductLength will contain between 1 and 50 elements, inclusive.
-
toJunction, fromJunction, and ductLength must all contain the same number of elements.
-
Every element of fromJunction will be between 0 and 49 inclusive.
-
Every element of toJunction will be between 1 and 49 inclusive.
-
fromJunction[i] will be less than toJunction[i] for all valid values of i.
-
Every (fromJunction[i],toJunction[i]) pair will be unique for all valid values of i.
-
Every element of ductlength will be between 1 and 2000000 inclusive.
-
The graph represented by the set of edges (fromJunction[i],toJunction[i]) will never contain a loop, and all junctions can be reached from junction 0.
Examples
0)
{0}
{1}
{10}
Returns: 10
The simplest sewer system possible. Your technician would first check transformer 0, travel to junction 1 and check transformer 1, completing his check. This will take 10 minutes.
1)
{0,1,0}
{1,2,3}
{10,10,10}
Returns: 40
Starting at junction 0, if the technician travels to junction 3 first, then backtracks to 0 and travels to junction 1 and then junction 2, all four transformers can be checked in 40 minutes, which is the minimum.
2)
{0,0,0,1,4}
{1,3,4,2,5}
{10,10,100,10,5}
Returns: 165
Traveling in the order 0-1-2-1-0-3-0-4-5 results in a time of 165 minutes which is the minimum.
3)
{0,0,0,1,4,4,6,7,7,7,20}
{1,3,4,2,5,6,7,20,9,10,31}
{10,10,100,10,5,1,1,100,1,1,5}
Returns: 281
Visiting junctions in the order 0-3-0-1-2-1-0-4-5-4-6-7-9-7-10-7-8-11 is optimal, which takes (10+10+10+10+10+10+100+5+5+1+1+1+1+1+1+100+5) or 281 minutes.
4)
{0,0,0,0,0}
{1,2,3,4,5}
{100,200,300,400,500}
Returns: 2500
简单分析：
此题有点类似遍历树，要满足题目要求，则必然满足如下性质：
1）在遍历结束时，必然停在一个叶子处。
2）在遍历结束是，每条树枝（即，连接相邻两个结点的路径）最多路过两次，最少路过一次。
3）假设，现在我们有个根R,他有n个分支（child），满足条件的遍历结束后，我们停在了第i个分支的一个叶子上，则，必然除第i个分支外的，其他n-1个分支中的各个路径都走了两遍。
算法：
我们规定一些函数名及其意义：
singleCycle(...)：参数，root的index，以及其他三个数组，返回值是该树，满足条件的遍历结果（即，最少所花时间）
{
对于root的每个分支，做一次singleCycle(...)和一次doubleCycle(...) （这里是递归调用）
再把两个的差存入一个数组，
如果root就是一个叶子，则返回0；否则返回 doubleCycle(...)与数组中取最大值的差值。
}
doubleCycle(...)：参数，root的index，以及其他三个数组,返回值是该树所有路径都走两边的值。
原理是，对于每个分支，我们都可以在分支中的各个路径走两遍，也可以按照时间最小化走，两者的差就是我们节省的时间，当然我们选择了在这个分支上时间最小化，则在其他分支上，必定是走两遍的。所以我们要选择个一个分支按时间最小化的方法走，使得我们在n个节省时间中，节省的时间最多，则总体的时间就用得最少。
#include <iostream>
#include <math.h>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
class PowerOutage
{
private:
vector<int> doubleCycleTable;
public:
int doubleCycle(int root,vector <int> fromJunction, vector <int> toJunction, vector <int> ductLength)
{
int res=0;
bool isLeave = true;
for(int i=0;i<fromJunction.size();i++)
if(fromJunction[i]==root)
{
isLeave=false;
res+=2*ductLength[i]+doubleCycle(toJunction[i],fromJunction,toJunction,ductLength);
}
return isLeave ? 0 : res;
}
int singleCycle(int root,vector <int> fromJunction, vector <int> toJunction, vector <int> ductLength)
{
vector<int> delta;
bool isLeave = true;
for(int i=0;i<fromJunction.size();i++)
if(fromJunction[i]==root)
{
isLeave=false;
delta.push_back(ductLength[i]+doubleCycle(toJunction[i],fromJunction,toJunction,ductLength)
-singleCycle(toJunction[i],fromJunction,toJunction,ductLength));
}
return isLeave ? 0 : (doubleCycle(root,fromJunction,toJunction,ductLength)-*max_element(delta.begin(),delta.end()));
}
int estimateTimeOut(vector <int> fromJunction, vector <int> toJunction, vector <int> ductLength)
{
return singleCycle(0,fromJunction,toJunction,ductLength);
}
};
Feb 18, 2019 08:56:17 AM
All the hurdles are strangled for the good and all followed items or the people. The chip of the theme and uk.bestessays is approved for the individuals. The mutual stance is done for the flow of the marks for the star and such high level of the elements for the humans in life.
May 04, 2022 04:34:05 PM
Every once in a while I find something worth reading when I’m surfing the internet. Bravo… thanks for creating real content here… How to Start a Merchant Services Business
===================================================================
For my part, the particular was presented an employment which is non secular enlargement. Payment Processing Reseller
===================================================================
This can be a remarkably amazing powerful resource that you’re offering and you simply provide it away cost-free!! I comparable to discovering websites ones comprehend the particular importance of supplying you with a excellent learning resource for zero cost. We truly dearly loved examining these pages. Appreciate it! Tips on Selling Merchant Services
Jul 09, 2022 06:24:13 AM
I definitely did not understand that. Learnt one thing new today! Thanks for that. 回收手提電腦
========================
hey there i stumbled upon your site searching around the web. I wanted to tell you I enjoy the look of things around here. Keep it up will bookmark for sure. iphone回收價
=============================
I agree with your thoughts here and I really love your blog! I’ve bookmarked it so that I can come back & read more in the future. 雲台
Jul 19, 2022 10:23:21 PM
What a sensational blog! This blog is too much amazing in all aspects. Especially, it looks awesome and the content available on it is utmost qualitative. Woking to Heathrow Taxi
Feb 09, 2023 02:16:23 PM
What are you stating, man? I realize everyones got their own view, but really? Listen, your web site is neat. I like the energy you put into it, especially with the vids and the pics. But, come on. Theres gotta be a better way to say this, a way that doesnt make it seem like everyone here is stupid! Software Contract Attorney
Apr 23, 2023 01:45:42 PM
crediblebh