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;
}