问最优树遍历算法Topcoder
EN

Code Review用户

提问于 2016-01-15 04:40:29

回答 1查看 244关注 0票数 3

我正在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;
}

代码运行良好，并通过了所有测试用例。有什么办法让我改进吗？

java

algorithm

programming-challenge

tree

回答 1

Code Review用户

发布于 2016-01-20 01: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;
}