用Java... 一直TLE 求问为啥 (50%通过率)

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.Map.Entry;
import java.lang.*;

import java.text.*;

public class Main {
    private static int maxProfit = 0;
    private static Node[] nodes;
    private static int source;
    private static int end;
    private static Stack<Node> stack = new Stack<>();
    
    private static class Node {
        int id;
        int price;
        int status;
        int step;
        int low;
        boolean queried = false;
        int bestProfit = 0;
        int bestSellPrice = 0;
        
        Node component = this;
        Boolean reachableToEnd = false;
        HashSet<Node> outNodes = new HashSet<>();
        HashSet<Node> outComponents = new HashSet<>();
        HashSet<Node> componentNodes = new HashSet<>();
        
        int buyPrice = 0;
        int sellPrice = 0;
        
        Node (int id, int price)
        {
            this.id = id;
            this.price = price;
            this.buyPrice = price;
            this.sellPrice = price;
            this.status = 0;
            this.step = 0;
        }
    }
    
    public static void main(String[] args) throws IOException {
        String fileName = "input_1754.txt";
        //boolean debugging = true;
        boolean debugging = false;
        
        //Scanner scanner = debugging? new Scanner(new FileInputStream(fileName)) : new Scanner(System.in) ;
        BufferedReader reader = debugging? new BufferedReader(new InputStreamReader(new FileInputStream(fileName))) : new BufferedReader(new InputStreamReader(System.in));
        
        //String[] nums = scanner.nextLine().trim().split("\\s");
        String[] nums = reader.readLine().split(" ");
        int n = Integer.valueOf(nums[0]);
        int m = Integer.valueOf(nums[1]);
        source = 1;
        end = n;
        
        nodes = new Node[n+1];
        //nums = scanner.nextLine().trim().split("\\s");
        nums = reader.readLine().split(" ");
        for(int i = 1; i <= nums.length; i++)
        {
            int id = i;
            int price = Integer.valueOf(nums[i-1]);
            nodes[i] = new Node(id, price);
        }

        for (; m > 0; m--)
        {
            //nums = scanner.nextLine().trim().split("\\s");
            nums = reader.readLine().split(" ");
            int idA = Integer.valueOf(nums[0]);
            int idB = Integer.valueOf(nums[1]);
            int conns = Integer.valueOf(nums[2]);
            
            if (idA == idB)
            {
                continue;
            }
            
            nodes[idA].outNodes.add(nodes[idB]);
            if (conns == 2)
            {
                nodes[idB].outNodes.add(nodes[idA]);
            }
        }
        
        nodes[n].reachableToEnd = true;
        tarjan(nodes[1], nodes[1]);
        queryComponentNode(nodes[1].component);
        
        System.out.println(nodes[1].bestProfit);
    }
    
    private static int step = 0;
    
    private static void tarjan(Node node, Node source)
    {   
        if (node.status == 2)
        {
            return;
        }
        
        if (node.status == 1)
        {
            source.low = node.step;
            return;
        }
        
        node.status = 1;
        node.step = ++step;
        node.low = node.step;
        stack.add(node);
        
        for (Node outNode : node.outNodes)
        {
            tarjan(outNode, node);
        }
        
        source.low = Math.min(node.low, source.low);
        
        if (node.step == node.low)
        {
            //System.out.println("\nnode:"+node.id);
            while (!stack.isEmpty() && stack.peek().step >= node.step)
            {
                Node componentNode = stack.pop();
                componentNode.component = node;
                node.componentNodes.add(componentNode);
                node.sellPrice = Math.max(node.sellPrice, componentNode.sellPrice);
                node.buyPrice = Math.min(node.buyPrice, componentNode.buyPrice);
                node.reachableToEnd |= componentNode.reachableToEnd;
                
                for (Node outNode : componentNode.outNodes)
                {
                    //System.out.println("outNode:"+outNode.id +" componentId:" + outNode.component.id);
                    if (outNode.component.reachableToEnd && outNode.component.id != node.id)
                    {
                        node.outComponents.add(outNode.component);
                        node.reachableToEnd = true;
                        //System.out.println("out component:" + outNode.component.id);
                    }
                }
                
                //System.out.println(componentNode.id + " " + componentNode.buyPrice + " " + componentNode.sellPrice);
            }
            
            /*
            System.out.println("price:" + node.price);
            System.out.println("sellPrice:" + node.sellPrice);
            System.out.println("buyPrice:" + node.buyPrice);
            System.out.println("reachableToEnd:" + node.reachableToEnd);
            */
        }
        node.status = 2;
    }
    
    private static void queryComponentNode(Node node)
    {
        //System.out.println("querying node:" + node.id);
        if (node.queried)
        {
            return;
        }
        
        node.queried = true;
        int bestSellPrice = 0;
        int bestProfit = 0;
        
        for (Node outComponent : node.outComponents)
        {
            queryComponentNode(outComponent);
            bestSellPrice = Math.max(bestSellPrice, outComponent.bestSellPrice);
            bestProfit = Math.max(bestProfit, outComponent.bestProfit);
        }
        
        node.bestSellPrice = Math.max(node.sellPrice, bestSellPrice);
        node.bestProfit = Math.max(node.bestSellPrice - node.buyPrice, bestProfit);
    }
}

2 条评论

  • @ 2017-06-07 14:36:19

    因为玩mc才学java的吧。。

  • @ 2017-03-30 01:42:16

    如果您的算法时间复杂度是平方的(可以自行尝试测试一些大规模的数据,可以把读入部分修改为直接随机生成数据,然后利用vijos自带的“自测”进行评测),请检查是否是读入超时。因为读入数据的量比较大。

  • 1

信息

ID
1754
难度
6
分类
图结构 | 最短路 点击显示
标签
递交数
2908
已通过
747
通过率
26%
被复制
10
上传者