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 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:
int[], int[], int[]
Returns:
int
Method signature:
int estimateTimeOut(int[] fromJunction, int[] toJunction, 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
我没有很好的想法，参考一些提交者的算法，比较典型的是下面这一种：//from CN_Rigel
public class PowerOutage{
public static int estimateTimeOut(int From[],int[] to,int cost[]){
int Time=0;
for(int i=0;i<to.length;i++){
Time+=2*cost[i];
}
Time-=FindMax(0,From,to,cost);
return Time;
}
static int FindMax(int start,int From[],int to[],int cost[]){
int result=0;
for(int i=0;i<From.length;i++){
int max=0;
if(From[i]==start){
max+=cost[i];
max+=FindMax(to[i],From,to,cost);
if(max>result)
result=max;
}
}
return result;
}
}很佩服这位作者，本来以为会有很长一段代码，但他采用了逆向求解的方法借助递归来完成只用了几十行。经测试该算法是正确的，但我还有些疑问，一是为什么会存在这种最大与最小值之间的互补关系 ，二是关于这个递归的使用思路希望有高人可以指点一下
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 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:
int[], int[], int[]
Returns:
int
Method signature:
int estimateTimeOut(int[] fromJunction, int[] toJunction, 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
我没有很好的想法，参考一些提交者的算法，比较典型的是下面这一种：//from CN_Rigel
public class PowerOutage{
public static int estimateTimeOut(int From[],int[] to,int cost[]){
int Time=0;
for(int i=0;i<to.length;i++){
Time+=2*cost[i];
}
Time-=FindMax(0,From,to,cost);
return Time;
}
static int FindMax(int start,int From[],int to[],int cost[]){
int result=0;
for(int i=0;i<From.length;i++){
int max=0;
if(From[i]==start){
max+=cost[i];
max+=FindMax(to[i],From,to,cost);
if(max>result)
result=max;
}
}
return result;
}
}很佩服这位作者，本来以为会有很长一段代码，但他采用了逆向求解的方法借助递归来完成只用了几十行。经测试该算法是正确的，但我还有些疑问，一是为什么会存在这种最大与最小值之间的互补关系 ，二是关于这个递归的使用思路希望有高人可以指点一下
*****************************************************************************
欢迎使用CSDN论坛专用阅读器 : CSDN Reader(附全部源代码) http://feiyun0112.cnblogs.com/
我采用了穷举法，用递归实现：
import java.util.*;
public class PowerOutage{
static int min=Integer.MAX_VALUE; //最小路径
static int junctionCount=0; //总的顶点数
static List<Integer> minPath=null; //路径。
public static void main(String[] args){
/*int[] fromJunction={0,1,0};
int[] toJunction={1,2,3};
int[] ductLength={10,10,10};
int[] fromJunction={0};
int[] toJunction={1};
int[] ductLength={10};
int[] fromJunction={0,0,0,1,4};
int[] toJunction={1,3,4,2,5};
int[] ductLength={10,10,100,10,5};*/
int[] fromJunction={0,0,0,1,4,4,6,7,7,7,8};
int[] toJunction={1,3,4,2,5,6,7,8,9,10,11};
int[] ductLength={10,10,100,10,5,1,1,100,1,1,5};
System.out.println("Min Time:"+estimateTimeOut(fromJunction,toJunction,ductLength));
System.out.println(""+minPath);
}
public static int estimateTimeOut(int[] fromJunction, int[] toJunction, int[] ductLength) {
Set<Integer> jun=new TreeSet<Integer>();
for(int i=0;i<fromJunction.length;i++){
jun.add(fromJunction[i]);
}
for(int i=0;i<fromJunction.length;i++){
jun.add(toJunction[i]);
}
junctionCount=jun.size(); //上面的两个循环就是为了得到总的节点数（顶点数）
int start=0;
List<Integer> path=new ArrayList<Integer>();
path.add(0);
int[] flag=new int[junctionCount];
flag[0]=1;
travel(start,fromJunction,toJunction,ductLength,path,0);
return min;
}
/*@param start 开始遍历的顶点。
* @param count 计数遍历过的顶点数
* @param path 存放路径
* @param cost 路径长
* @param plag 标识数组，遍历过的标识为1
* 递归调用
*/
static void travel(int start,int[] from,int[] to,int[] ductLength,List<Integer> path,int cost){
if(transferAll(path)){ //得到结果
if(cost<min){ //如果比最小的路径长还小
min=cost;
minPath=new ArrayList<Integer>(path);
return ;
}
}
List <Integer> adj=new ArrayList<Integer>(); //把所有的和start邻接的点及路径长都放在adj中.
for(int i=0;i<from.length;i++){
if(from[i]==start){
adj.add(to[i]);
adj.add(ductLength[i]);
}
}
for(int i=0;i<to.length;i++){
if(to[i]==start){
adj.add(from[i]);
adj.add(ductLength[i]);
}
} Iterator<Integer> it=adj.iterator();
while(it.hasNext()){
int next=it.next();
if(!isCycle(path,start,next)){ //下一步不会构成环
//path=new ArrayList<Integer>(path);
path.add(next); //加入路径
travel(next,from,to,ductLength,path,cost+it.next());
path.remove(path.size()-1);
}else{
it.next();
}
}
}
static boolean isCycle(List<Integer> path,int one,int nextone){ //从one 到nextone是不是走过,并且是环的一部分.
Object[] pathArray=path.toArray();
if(pathArray.length<2) return false;
int p=0,q=p+1;
while(q<pathArray.length){
if((Integer)(pathArray[p])==one&&(Integer)(pathArray[q])==nextone) return true;
p=q;
q++;
}
return false;
}
static boolean transferAll(List<Integer> path){ //在路径中是不是包含了全部的顶点
Set<Integer> jun=new HashSet<Integer>(path);
if(jun.size()==junctionCount) return true;
return false;
}}
* @param plag 标识数组，遍历过的标识为1这两个在注释中的参数没有用了,原来用这两个参数来判断是不是所有的顶点都访问过了.后来改用一个方法来判断:static boolean transferAll(List<Integer> path)这个方法名起的不好.原文中有transformer这个词,我随手打成了transfer.
还有一个小问题请教：你设立的junctioncount似乎并不是严格的节点数，是怎么考虑的？要知道from和to数组有重复节点
我还没有看懂原贴的程序。
junctioncount是正确的节点数，我把所有出现的节点，都扔到set中了，再由set的大小得到了节点数。set中是不能有重复元素的。
int[] fromJunction,
int[] toJunction,
int[] ductLength
这三个数组中元素的排列规则。
｛0，1，2，3｝
｛1，2，3，0｝
｛10，10，10，10｝
如果这样排列，你给出的程序会出现死循环。但正如我怀疑的，他的程序之所以不会死循环是因为那三个数组不能象上面的那样排列。上面的数组应该排为：
｛0，1，2，0｝
｛1，2，3，3｝
｛10，10，10，10｝
甚至于三个顶点最多给出三条边，最后一给边都可以去掉。
你给出的程序我看明白了，他的意思是这样的，他假设了第一条边都经过两次，他再把从0点出发一直向前走，直到走不动（到了某点后，在from数组中找不到这个点），计算这时的路径长，再在这所有的路径长中取最大的。把这条最大的路径长减去可以了。
意思就是他先把其它路径走完后，最后再走那条最长的路径，走完后，所有的结点都访问过了，这样就不用从最长的路径返回去了。
意思就是他先把其它路径走完后，最后再走那条最长的路径，走完后，所有的结点都访问过了，这样就不用从最长的路径返回去了。