- 最优贸易
- 2017-03-29 19:02:16 @
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 条评论
-
SW_Wind LV 8 @ 2017-06-07 14:36:19
因为玩mc才学java的吧。。
-
2017-03-30 01:42:16@
如果您的算法时间复杂度是平方的(可以自行尝试测试一些大规模的数据,可以把读入部分修改为直接随机生成数据,然后利用vijos自带的“自测”进行评测),请检查是否是读入超时。因为读入数据的量比较大。
- 1