最优树遍历算法Topcoder
我正在topcoder.com舞台上练习一个1000点的算法问题。
问题如下：
你在一家电力公司工作，在一个相当大的公寓里停电，那里有很多愤怒的房客。你把问题隔离到复杂建筑下面的下水道网络中，在管道迷宫的每一个交界处都有一个升级变压器。在恢复电源之前，必须检查每台变压器是否正常运行，必要时予以固定。更糟糕的是，下水道被布置成一棵树，树根位于下水道网络的入口处。这意味着，为了从一个变压器到下一个变压器，将有许多回溯通过长期和幽闭恐惧症的管道，因为没有捷径之间的连接。此外，这是一个星期天，你只有一个值班的技术人员在下水道网络中搜索坏的变压器。你的主管想知道你有多快才能恢复供电；他太不耐烦了，他想在技术员接上最后一台变压器的那一刻就恢复供电，甚至不用等技术员先离开下水道。
您将得到三个int[]'s: fromJunction，toJunction，和ductLength，代表每个下水道管道。导管I在连接处(fromJunction我)开始，并通向连接处(toJunction我)。导管长度我表示技术人员穿过连接fromJunction我和toJunction我的管道所需的分钟数。考虑一下您的技术员检查/修理变压器所需的时间是瞬间的。你的技术人员将从0路口开始，这是下水道系统的根部。你的目标是计算出你的技术员检查所有变压器所需的最少分钟数。您将返回一个int，它表示这个最小分钟数。
约束：
- fromJunction将包含1到50个元素(含)。
- toJunction将包含1到50个元素(含)。
- ductLength将包含1到50个元素(含)。
- toJunction、fromJunction和ductLength都必须包含相同数量的元素。
- fromJunction的每个元素都包含在0到49之间。
- toJunction的每个元素都包含在1到49之间。
- 对于i的所有有效值，fromJunction我将小于toJunction我。
- 对于i的所有有效值，每个(fromJunction我，toJunction我)对都是唯一的。
- 导管长度的每一个元素都包含在1到2000000之间。
- 由边缘集(fromJunction我，toJunction我)表示的图永远不会包含循环，所有的连接都可以从连接0到达。
示例测试用例：
通过测试
{0,0,0,1,4}
{1,3,4,2,5}
{10，10,100，10
返回:165个
{0，0，0，0，1，4，6，7，7，20}
{1,3,4,2,5,6,7,20,9,10,31}
{10，10 100，10，5，1,100，1，1，5}
返回: 281
{0、0、1、1、1、3、1、4、7、2、0、3、6、8、5、11、3、12、0、15、15、18、0、4、7、24、25、10、0、19、25、6、15、29、20、5、23、19}
{1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、19、20、21、22、23、24、25、26、27、28、29、30、31、32、33、34、35、36、37、38}
{178317、81669、294672、1649827、671297、443274、1823848、333826、1750416、289900、1922826、1961031、1984157、1022042、1708788、952091、1095097、1600638、1896461、288397、741380、540242、1094958、60081、950467、1955292、1607609、1717760、1318832、242398、1586217、1374294、1231329、1969383、562578、962458、1114049、313948}
返回: 78008798
通过测试
{0、0、0、0、1、0、3、2、6、4、0、2、11、3、1、14、3、2、5、15、6、0、11、8、11、24、23、6、22、2、15、20、4、22、30、14、5、9、7、7、36、15、34、3、2}
{1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、19、20、21、22、23、24、25、26、27、28、29、30、31、32、33、34、35、36、37、38、39、40、41、42、43、44、45}
{752846、1419859、179904、163605、1740377、190846、1352634、965272、824872、538518、1438990、714089、1749318、238531、429771、1075929、996791、634327、687236、1567508、1123950、68018、1617650、191391、571448、1348412、164008、205801、1063191、1117957、1692178、1234376、1504523、1015591、1828379、1224921、1545579、37373、14625、379669、18141、18986、2586、764261717177、1763191、1117957、1692178、1234376、1504523、1015591、1828379、1224921、1545579、37373、14625、379669、18141、18986、2586、76428281717177}{{752846、1419859、179904、163605、1740377、190846、1352634、965272、824872、538518、1438990、714089、1749318、238531、429771、1015591、1828379、1224921、1545579、37373、14625、379669、18141、18986、764282177}
预期: 83927521
收到: 83927521
代码：
import java.util.*;
public class PowerOutage {
public int estimateTimeOut(int[] fromJunction, int[] toJunction, int[] ductLength) {
int res = 0, len = fromJunction.length;
for (int i = 0; i < len; i++) {
res += ductLength[i] * 2;
}
return res - mostExpensivePath(fromJunction, toJunction, ductLength, 0);
}
public boolean count(int[] a, int node) {
for (int i = 0; i < a.length; i++) {
if (a[i] == node)
return false;
}
return true;
}
//Depth First Search
public int mostExpensivePath(int[] a, int[] b, int[] c, int currentRoot) {
int cost = 0, maxC = 0, k = a.length, tempC = 0;
while (!done(c)) {
//find first deepest leaf node
for (int i = 0; i < k; i++) {
if (a[i] == currentRoot) {
currentRoot = b[i];
cost += c[i];
i = -1;
}
}
//trace leaf node back to the first multi-node parent
for (int i = 0; i < k; i++) {
if (b[i] == currentRoot) {
currentRoot = a[i];
a[i] = -1;
b[i] = -1;
tempC += c[i];
c[i] = 0;
i = -1;
if (!count(a, currentRoot))
break;
}
}
//check cost is max
if (cost > maxC)
maxC = cost;
cost -= tempC;
tempC = 0;
}
return maxC;
}
public boolean done(int[] c) {
for (int i = 0; i < c.length; i++) {
if (c[i] > 0)
return false;
}
return true;
}代码运行良好，并通过了所有测试用例。有什么办法让我改进吗？
回答 1
Code Review用户
发布于 2016-01-20 09:43:32
更简单(但在某些情况下非常慢)函数计算最长路径的成本：
public int largestPathCost(int[] a, int[] b, int[] c) {
int k = a.length;
// prepare array of costs (times) to reach each node
int cost[] = new int[k+1];
for (int i = 0; i <= k; i++)
cost[i] = 0;
// calculate times by adding duct lengths
for (int toGo = k; toGo != 0;) { // nodes to calculate
for (int i = 0; i < k; i++) { // test the i-th duct
int fromId = a[i];
int toId = b[i]; // endpoint
if (cost[toId] == 0) // not calculated yet
if (fromId == 0 || cost[fromId] != 0) {
cost[toId] = cost[fromId] + c[i];
toGo --;
}
}
}
// retrieve the maximum cost
int maxC = 0;
for (int i = 1; i <= k; i++) {
if (cost[i] > maxC)
maxC = cost[i];
}
return maxC;
}如果管道是以相反的顺序(最远的第一个)提供的话，它可能会非常慢。最糟糕的情况是单程“迷宫”，长链的管道没有叉子，管道按“向后”的顺序排列。这将导致k迭代k-item数组，从而导致O(k^2)的总时间开销。
为了避免最坏的情况，您可以在分析之前增加toJunction[]值来对这三个输入数组进行排序。然后将实际分析简化为一次通过k-item数组，因此需要线性时间O(k)。加上排序的时间，总复杂度为O(k log )。
https://codereview.stackexchange.com/questions/116873
复制相似问题
腾讯云开发者
