SHARE
TWEET

Pump

a guest Dec 14th, 2019 106 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. import java.util.*;
  3. import java.io.*;
  4.  
  5. class FastScanner {
  6.     public BufferedReader br;
  7.     public StringTokenizer st;
  8.  
  9.     public FastScanner(InputStream is) throws IOException {
  10.         br = new BufferedReader(new InputStreamReader(is), 32768);
  11.         st = null;
  12.     }
  13.  
  14.     public String next() {
  15.         while (st == null || !st.hasMoreTokens()) {
  16.             try {
  17.                 st = new StringTokenizer(br.readLine());
  18.             } catch (IOException e) {
  19.                 throw new RuntimeException(e);
  20.             }
  21.         }
  22.         return st.nextToken();
  23.     }
  24.  
  25.     public int nextInt() {
  26.         return Integer.parseInt(next());
  27.     }
  28.  
  29.     public long nextLong() {
  30.         return Long.parseLong(next());
  31.     }
  32.  
  33.     public double nextDouble() {
  34.         return Double.parseDouble(next());
  35.     }
  36.  
  37.     public String nextLine() {
  38.         String str = "";
  39.         try {
  40.             str = br.readLine();
  41.         } catch (IOException e) {
  42.             throw new RuntimeException(e);
  43.         }
  44.         return str;
  45.     }
  46. }
  47.  
  48. class Edge {
  49.     private int fromNodeIndex;
  50.     private int toNodeIndex;
  51.     private int length;
  52.  
  53.     public Edge(int fromNodeIndex, int toNodeIndex, int length) {
  54.         this.fromNodeIndex = fromNodeIndex;
  55.         this.toNodeIndex = toNodeIndex;
  56.         this.length = length;
  57.     }
  58.  
  59.     public int getFromNodeIndex() {
  60.         return fromNodeIndex;
  61.     }
  62.  
  63.     public int getToNodeIndex() {
  64.         return toNodeIndex;
  65.     }
  66.  
  67.     public int getLength() {
  68.         return length;
  69.     }
  70.  
  71.     public int getNeighbourIndex(int nodeIndex) {
  72.         if (this.fromNodeIndex == nodeIndex) {
  73.             return this.toNodeIndex;
  74.         } else {
  75.             return this.fromNodeIndex;
  76.         }
  77.     }
  78.  
  79.     public String toString() {
  80.         return fromNodeIndex + " " + toNodeIndex + " " + length;
  81.     }
  82. }
  83.  
  84. class Node {
  85.     private int distanceFromSource = Integer.MAX_VALUE;
  86.     private boolean visited;
  87.     private ArrayList<Edge> edges = new ArrayList<Edge>();
  88.  
  89.     public int getDistanceFromSource() {
  90.         return distanceFromSource;
  91.     }
  92.  
  93.     public void setDistanceFromSource(int distanceFromSource) {
  94.         this.distanceFromSource = distanceFromSource;
  95.     }
  96.  
  97.     public boolean isVisited() {
  98.         return visited;
  99.     }
  100.  
  101.     public void setVisited(boolean visited) {
  102.         this.visited = visited;
  103.     }
  104.  
  105.     public ArrayList<Edge> getEdges() {
  106.         return edges;
  107.     }
  108.  
  109.     public void setEdges(ArrayList<Edge> edges) {
  110.         this.edges = edges;
  111.     }
  112. }
  113.  
  114. class Graph {
  115.     private Node[] nodes;
  116.     private int noOfNodes;
  117.     private Edge[] edges;
  118.     private int noOfEdges;
  119.  
  120.     public Graph(Edge[] edges) {
  121.         this.edges = edges;
  122.         this.noOfNodes = calculateNoOfNodes(edges);
  123.         this.nodes = new Node[this.noOfNodes];
  124.         for (int n = 0; n < this.noOfNodes; n++) {
  125.             this.nodes[n] = new Node();
  126.         }
  127.         this.noOfEdges = edges.length;
  128.         for (int edgeToAdd = 0; edgeToAdd < this.noOfEdges; edgeToAdd++) {
  129.             this.nodes[edges[edgeToAdd].getFromNodeIndex()].getEdges().add(edges[edgeToAdd]);
  130.             this.nodes[edges[edgeToAdd].getToNodeIndex()].getEdges().add(edges[edgeToAdd]);
  131.         }
  132.     }
  133.  
  134.     private int calculateNoOfNodes(Edge[] edges) {
  135.         int noOfNodes = 0;
  136.         for (Edge e : edges) {
  137.             if (e.getToNodeIndex() > noOfNodes)
  138.                 noOfNodes = e.getToNodeIndex();
  139.             if (e.getFromNodeIndex() > noOfNodes)
  140.                 noOfNodes = e.getFromNodeIndex();
  141.         }
  142.         noOfNodes++;
  143.         return noOfNodes;
  144.     }
  145.  
  146.     public void calculateShortestDistances() {
  147.         this.nodes[0].setDistanceFromSource(0);
  148.         int nextNode = 0;
  149.         for (int i = 0; i < this.nodes.length; i++) {
  150.             ArrayList<Edge> currentNodeEdges = this.nodes[nextNode].getEdges();
  151.             for (int joinedEdge = 0; joinedEdge < currentNodeEdges.size(); joinedEdge++) {
  152.                 int neighbourIndex = currentNodeEdges.get(joinedEdge).getNeighbourIndex(nextNode);
  153.                 if (!this.nodes[neighbourIndex].isVisited()) {
  154.                     int tentative = this.nodes[nextNode].getDistanceFromSource()
  155.                             + currentNodeEdges.get(joinedEdge).getLength();
  156.                     if (tentative < nodes[neighbourIndex].getDistanceFromSource()) {
  157.                         nodes[neighbourIndex].setDistanceFromSource(tentative);
  158.                     }
  159.                 }
  160.             }
  161.             nodes[nextNode].setVisited(true);
  162.             nextNode = getNodeShortestDistanced();
  163.         }
  164.     }
  165.  
  166.     private int getNodeShortestDistanced() {
  167.         int storedNodeIndex = 0;
  168.         int storedDist = Integer.MAX_VALUE;
  169.         for (int i = 0; i < this.nodes.length; i++) {
  170.             int currentDist = this.nodes[i].getDistanceFromSource();
  171.             if (!this.nodes[i].isVisited() && currentDist < storedDist) {
  172.                 storedDist = currentDist;
  173.                 storedNodeIndex = i;
  174.             }
  175.         }
  176.         return storedNodeIndex;
  177.     }
  178.  
  179.     public int getDist(){
  180.         return nodes[nodes.length - 1].getDistanceFromSource();
  181.     }
  182.  
  183.     public Node[] getNodes() {
  184.         return nodes;
  185.     }
  186.  
  187.     public int getNoOfNodes() {
  188.         return noOfNodes;
  189.     }
  190.  
  191.     public Edge[] getEdges() {
  192.         return edges;
  193.     }
  194.  
  195.     public int getNoOfEdges() {
  196.         return noOfEdges;
  197.     }
  198. }
  199.  
  200. public class Main {
  201.     public static void main(String[] args) throws IOException {
  202.         InputStream is = new FileInputStream("pump.in");
  203.         PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("pump.out")));
  204.         FastScanner sc = new FastScanner(is);
  205.  
  206.         int N = sc.nextInt();
  207.         int M = sc.nextInt();
  208.  
  209.         Edge[] edges = new Edge[M];
  210.         int n1, n2, f, c;
  211.         ArrayList<Integer> flows = new ArrayList<Integer>();
  212.  
  213.         for (int i = 0; i < M; i++) {
  214.             n1 = sc.nextInt();
  215.             n2 = sc.nextInt();
  216.  
  217.             c = sc.nextInt();
  218.             f = sc.nextInt();
  219.  
  220.             edges[i] = new Edge(n1 - 1, n2 - 1, c);
  221.             flows.add(f);
  222.         }
  223.         for (int i = 0; i < edges.length; i++) {
  224.             System.out.println(edges[i]);
  225.         }
  226.         Graph g = new Graph(edges);
  227.         g.calculateShortestDistances();
  228.  
  229.         int cost = g.getDist();
  230.         int flow = min(flows);
  231.         int out = (1000000 * flow)/cost;
  232.         System.out.println(out);
  233.         pw.write(out);
  234.     }
  235.     public static int min(ArrayList<Integer> arr){
  236.         int ret = 10000;
  237.         for(int i: arr){
  238.             if(i < ret){
  239.                 ret = i;
  240.             }
  241.         }
  242.         return ret;
  243.     }
  244.  
  245. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top