Adding Solutions

Basic Debugging

Choosing a Language

Contest Strategy

Contests

Contributing

C++ With the Command Line

Data Types

How to Debug

Debugging C++

Expected Knowledge

Fast Input & Output

(Optional) C++ - Writing Generic Code

Input & Output

Introduction to Competitive Programming

(Optional) C++ - Lambda Expressions

Resources: Learning to Code

Introducing Modules

Olympiads

How to Practice

Resources: Competitive Programming

Resources: USA-Specific

Running Code Locally

Running Code Online

USACO Camp

USACO FAQs

USACO Monthlies

Using This Guide

Working With MDX

Ad Hoc Problems

Casework

Complete Search with Recursion

Additional Practice for USACO Bronze

Basic Complete Search

Introduction to Data Structures

Introduction to Graphs

Introduction to Greedy Algorithms

Introduction to Sets & Maps

Introduction to Sorting

Rectangle Geometry

Simulation

Time Complexity

Binary Search

Binary Search on a Sorted Array

Additional Practice for USACO Silver

Flood Fill

Introduction to Functional Graphs

Graph Traversal

Greedy Algorithms with Sorting

Intro to Bitwise Operators

Introduction to Tree Algorithms

More on Prefix Sums

Introduction to Prefix Sums

Priority Queues

Custom Comparators and Coordinate Compression

Two Pointers

DP on Trees - Solving For All Roots

Combinatorics

Additional Practice for USACO Gold

(Optional) Sorted Sets with Custom Comparators

Bitmask DP

Range DP

DP on Trees - Introduction

Disjoint Set Union

Digit DP

Divisibility

Hashing

(Optional) Hashmaps

Introduction to DP

More Operations on Sorted Sets

Knapsack DP

(Optional) LCA with Euler Tour

Longest Increasing Subsequence

Minimum Spanning Trees

(Optional) Meet In The Middle

Modular Arithmetic

Point Update Range Sum

Paths on Grids

Shortest Paths with Non-Negative Edge Weights

Sliding Window

Stacks

Optimizing Unimodal Functions

Topological Sort

(Optional) Euler Tour Technique

Shortest Paths with Unweighted Edges

2D Range Queries

Binary Jumping

(Optional) Bitsets

Centroid Decomposition

Additional Practice for USACO Platinum

Convex Hull

Convex Hull Trick

Divide & Conquer - DP

Divide & Conquer - SRQ

Sum over Subsets DP

Geometry Primitives

Heavy-Light Decomposition

Matrix Exponentiation

Small-To-Large Merging

Inclusion-Exclusion Principle

Bellman-Ford, Floyd-Warshall, and Dijkstra.

Resource

Resources

title

Optional

problem

FocusProblem

CPPSection

JavaSection

PySection

LanguageSection

problems

Problems

width

height

controls

source

video

Warning

hideSuggestProblemButton

Milk Pumping

"use strict";
const {Fragment: _Fragment, jsx: _jsx, jsxs: _jsxs} = arguments[0];
const frontmatter = undefined;
function _createMdxContent(props) {
 const _components = {
 a: "a",
 code: "code",
 h2: "h2",
 p: "p",
 pre: "pre",
 strong: "strong",
 ...props.components
 }, {CPPSection, HeaderLink, JavaSection, LanguageSection, MATHSPAN, PySection} = _components;
 if (!CPPSection) _missingMdxReference("CPPSection", true);
 if (!HeaderLink) _missingMdxReference("HeaderLink", true);
 if (!JavaSection) _missingMdxReference("JavaSection", true);
 if (!LanguageSection) _missingMdxReference("LanguageSection", true);
 if (!MATHSPAN) _missingMdxReference("MATHSPAN", true);
 if (!PySection) _missingMdxReference("PySection", true);
 return _jsxs(_Fragment, {
 children: [_jsx(_components.p, {
 children: _jsx(_components.a, {
 href: "http://www.usaco.org/current/data/sol_pump_gold_dec19.html",
 rel: "nofollow",
 target: "_blank",
 children: "Official Analysis (C++)"
 })
 }), "\n", _jsxs(_components.h2, {
 id: "explanation",
 children: [_jsx(_components.a, {
 "aria-hidden": "true",
 tabIndex: "-1",
 className: "anchor before",
 href: "#explanation",
 children: _jsx(HeaderLink, {})
 }), "Explanation"]
 }), "\n", _jsx(_components.p, {
 children: "The larger the denominator, the smaller the result will be. We also want to minimize the cost of the path. This hints at a shortest-path problem. Due to the low number of junction points, we can fix the minimum flow rate and search for the lowest cost path we could take."
 }), "\n", _jsxs(_components.h2, {
 id: "implementation",
 children: [_jsx(_components.a, {
 "aria-hidden": "true",
 tabIndex: "-1",
 className: "anchor before",
 href: "#implementation",
 children: _jsx(HeaderLink, {})
 }), "Implementation"]
 }), "\n", _jsxs(LanguageSection, {
 children: [_jsxs(CPPSection, {
 children: [_jsxs(_components.p, {
 children: [_jsx(_components.strong, {
 children: "Time Complexity:"
 }), " ", _jsx(MATHSPAN, {
 className: "language-math math-inline",
 latex: "\\mathcal{O}(M^2 \\log N + MN)",
 children: "<math xmlns=\"http://www.w3.org/1998/Math/MathML\"><semantics><mrow><mi mathvariant=\"script\">O</mi><mo stretchy=\"false\">(</mo><msup><mi>M</mi><mn>2</mn></msup><mi>log</mi><mo>⁡</mo><mi>N</mi><mo>+</mo><mi>M</mi><mi>N</mi><mo stretchy=\"false\">)</mo></mrow><annotation encoding=\"application/x-tex\">\\mathcal{O}(M^2 \\log N + MN)</annotation></semantics></math>O(M2logN+MN)"
 })]
 }), _jsx(_components.pre, {
 children: _jsx(_components.code, {
 className: "language-cpp",
 children: "#include <bits/stdc++.h>\nusing namespace std;\n\nstruct Edge {\n\tint v, c, fl;\n};\n\nint n, m;\nconst int PRECISION = 1e6;\nvector<vector<Edge>> adj;\n\nint dijkstra(int minf) {\n\tpriority_queue<pair<int, int>> pq;\n\tvector<int> cost(n, INT32_MAX);\n\tcost[0] = 0;\n\tpq.push({0, 0});\n\n\twhile (!pq.empty()) {\n\t\tpair<int, int> nxt = pq.top();\n\t\tpq.pop();\n\n\t\tif (nxt.second != cost[nxt.first]) { continue; }\n\n\t\tfor (Edge u : adj[nxt.first]) {\n\t\t\tint ct = u.c + nxt.second;\n\n\t\t\t/*\n\t\t\t * if the path has a flow value less\n\t\t\t * than our minimum, we can't consider it\n\t\t\t */\n\t\t\tif (u.fl < minf) { continue; }\n\n\t\t\t// path more optimal\n\t\t\tif (cost[u.v] > ct) {\n\t\t\t\tcost[u.v] = ct;\n\t\t\t\tpq.push({u.v, ct});\n\t\t\t}\n\t\t}\n\t}\n\treturn cost[n - 1] == INT32_MAX ? -1 : cost[n - 1];\n}\n\nint main() {\n\tfreopen(\"pump.in\", \"r\", stdin);\n\tfreopen(\"pump.out\", \"w\", stdout);\n\n\tcin >> n >> m;\n\n\tadj.resize(n);\n\tvector<int> flows;\n\tfor (int i = 0; i < m; i++) {\n\t\tint u, v, c, fl;\n\t\tcin >> u >> v >> c >> fl;\n\n\t\tflows.push_back(fl);\n\t\tadj[--u].push_back({--v, c, fl});\n\t\tadj[v].push_back({u, c, fl});\n\t}\n\n\tint ans = -1;\n\t// we only have to consider the flow values given to us\n\tfor (int flow : flows) {\n\t\tint cur = dijkstra(flow);\n\n\t\t// can't complete this path\n\t\tif (cur == -1) { continue; }\n\t\tdouble ratio = double(flow) / double(cur);\n\t\tans = max(ans, (int)(ratio * PRECISION));\n\t}\n\tcout << ans << '\\n';\n}\n"
 })
 })]
 }), _jsxs(PySection, {
 children: [_jsxs(_components.p, {
 children: [_jsx(_components.strong, {
 children: "Time Complexity:"
 }), " ", _jsx(MATHSPAN, {
 className: "language-math math-inline",
 latex: "\\mathcal{O}(M^2 \\log N + MN)",
 children: "<math xmlns=\"http://www.w3.org/1998/Math/MathML\"><semantics><mrow><mi mathvariant=\"script\">O</mi><mo stretchy=\"false\">(</mo><msup><mi>M</mi><mn>2</mn></msup><mi>log</mi><mo>⁡</mo><mi>N</mi><mo>+</mo><mi>M</mi><mi>N</mi><mo stretchy=\"false\">)</mo></mrow><annotation encoding=\"application/x-tex\">\\mathcal{O}(M^2 \\log N + MN)</annotation></semantics></math>O(M2logN+MN)"
 })]
 }), _jsx(_components.pre, {
 children: _jsx(_components.code, {
 className: "language-py",
 children: "import heapq\n\nwith open(\"pump.in\", \"r\") as infile:\n\tn, m = map(int, infile.readline().split())\n\n\tgraph = [[] for _ in range(n)]\n\tflow_rates = []\n\n\tfor _ in range(m):\n\t\ta, b, c, f = map(int, infile.readline().split())\n\t\tgraph[a - 1].append((b - 1, c, f))\n\t\tgraph[b - 1].append((a - 1, c, f))\n\t\tflow_rates.append(f)\n\n\ndef dijkstra(flow_rate: int) -> float:\n\n\tcost = [float(\"inf\")] * n\n\tcost[0] = 0 # start at FJ's farm\n\tqueue = [(0, 0)]\n\tcompleted = set()\n\n\twhile queue:\n\t\tcurr_cost, curr_node = heapq.heappop(queue)\n\n\t\tif curr_node in completed:\n\t\t\tcontinue\n\t\tcompleted.add(curr_node)\n\n\t\tfor adj_node, pipe_cost, pipe_flow in graph[curr_node]:\n\t\t\t# we ignore all routes with flow rates less than our set rate\n\t\t\tif pipe_flow < flow_rate:\n\t\t\t\tcontinue\n\t\t\tnew_cost = curr_cost + pipe_cost\n\t\t\tif new_cost < cost[adj_node]:\n\t\t\t\tcost[adj_node] = new_cost\n\t\t\t\theapq.heappush(queue, (cost[adj_node], adj_node))\n\n\treturn 0 if cost[n - 1] == float(\"inf\") else flow_rate / cost[n - 1]\n\n\nmax_worth = 0\nfor flow_rate in flow_rates:\n\tworth = dijkstra(flow_rate)\n\tif worth > max_worth:\n\t\tmax_worth = worth\n\nprint(int(max_worth * 10**6), file=open(\"pump.out\", \"w\"))\n"
 })
 })]
 }), _jsxs(JavaSection, {
 children: [_jsxs(_components.p, {
 children: [_jsx(_components.strong, {
 children: "Time Complexity:"
 }), " ", _jsx(MATHSPAN, {
 className: "language-math math-inline",
 latex: "\\mathcal{O}(M \\log N + N)",
 children: "<math xmlns=\"http://www.w3.org/1998/Math/MathML\"><semantics><mrow><mi mathvariant=\"script\">O</mi><mo stretchy=\"false\">(</mo><mi>M</mi><mi>log</mi><mo>⁡</mo><mi>N</mi><mo>+</mo><mi>N</mi><mo stretchy=\"false\">)</mo></mrow><annotation encoding=\"application/x-tex\">\\mathcal{O}(M \\log N + N)</annotation></semantics></math>O(MlogN+N)"
 })]
 }), _jsx(_components.pre, {
 children: _jsx(_components.code, {
 className: "language-java",
 children: "// Created by Qi Wang\nimport java.io.*;\nimport java.util.*;\n\npublic class pump {\n\tstatic int N;\n\tstatic int M;\n\tstatic List<Node>[] adjList;\n\tstatic boolean[] vist;\n\tstatic int[] costs;\n\tstatic int max = Integer.MIN_VALUE;\n\t@SuppressWarnings(\"unchecked\")\n\tpublic static void main(String[] args) throws IOException {\n\t\tInputReader in = new InputReader(\"pump.in\");\n\t\tN = in.nextInt();\n\t\tM = in.nextInt();\n\n\t\tadjList = new List[N];\n\n\t\tfor (int i = 0; i < N; i++) { adjList[i] = new ArrayList<>(); }\n\n\t\tfor (int i = 0; i < M; i++) {\n\t\t\tint from = in.nextInt() - 1;\n\t\t\tint to = in.nextInt() - 1;\n\t\t\tint cost = in.nextInt();\n\t\t\tint flow = in.nextInt();\n\n\t\t\tadjList[from].add(new Node(to, cost, flow));\n\t\t\tadjList[to].add(new Node(from, cost, flow));\n\t\t}\n\n\t\t// Since flow is 1000 at most, we can just iterate through every value.\n\t\t// Or you can just test the flow values present in testcase.\n\t\tfor (int minF = 0; minF <= 1000; minF++) {\n\t\t\tcosts = new int[N];\n\t\t\tArrays.fill(costs, Integer.MAX_VALUE);\n\t\t\tvist = new boolean[N];\n\t\t\t// Running dijkstra with the min flow that we set.\n\t\t\tint[] res = dijkstra(minF);\n\t\t\t// Failed getting to the destination\n\t\t\tif (res[0] < 0) continue;\n\t\t\tdouble frac = (double)res[1] / res[0];\n\t\t\t// Maxing so we have the maximal answer.\n\t\t\tmax = Math.max(max, (int)Math.floor(frac * 1e6));\n\t\t}\n\t\tPrintWriter out =\n\t\t new PrintWriter(new BufferedWriter(new FileWriter(\"pump.out\")));\n\t\tout.println(max);\n\t\tout.close();\n\t}\n\n\tpublic static int[] dijkstra(int minF) {\n\t\tPriorityQueue<Node> pq = new PriorityQueue<>();\n\t\tint min = Integer.MAX_VALUE;\n\t\tpq.add(new Node(0, 0, 0));\n\t\tcosts[0] = 0;\n\t\twhile (!pq.isEmpty()) {\n\t\t\tNode cur = pq.poll();\n\t\t\tint n = cur.No;\n\n\t\t\tif (vist[n]) continue;\n\t\t\tvist[n] = true;\n\n\t\t\tfor (int i = 0; i < adjList[n].size(); i++) {\n\t\t\t\tint t = adjList[n].get(i).No;\n\t\t\t\tint c = adjList[n].get(i).c + cur.c;\n\n\t\t\t\tif (adjList[n].get(i).f < minF) continue;\n\t\t\t\tif (vist[t]) continue;\n\n\t\t\t\tif (costs[t] > c) {\n\t\t\t\t\tcosts[t] = c;\n\t\t\t\t\tmin = Math.min(min, adjList[n].get(i).f);\n\t\t\t\t\tpq.add(new Node(t, c, adjList[n].get(i).f));\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t\treturn new int[] {costs[N - 1] == Integer.MAX_VALUE ? -1 : costs[N - 1], min};\n\t}\n\n\tprivate static class Node implements Comparable {\n\t\tint No;\n\t\tint c;\n\t\tint f;\n\t\tpublic Node(int n, int c, int f) {\n\t\t\tNo = n;\n\t\t\tthis.c = c;\n\t\t\tthis.f = f;\n\t\t}\n\n\t\t@Override\n\t\tpublic int compareTo(Object o) {\n\t\t\treturn c - ((Node)o).c;\n\t\t}\n\n\t\t@Override\n\t\tpublic String toString() {\n\t\t\treturn No + \" \" + c + \" \" + f;\n\t\t}\n\t}\n\n\tprivate static class InputReader {\n\t\tpublic BufferedReader reader;\n\t\tpublic StringTokenizer tokenizer;\n\n\t\tpublic InputReader() {\n\t\t\ttry {\n\t\t\t\treader = new BufferedReader(new InputStreamReader(System.in), 32768);\n\t\t\t} catch (Exception e) {\n\t\t\t\tthrow new NullPointerException(\"Could not create input stream\");\n\t\t\t}\n\t\t}\n\n\t\tpublic InputReader(String fileName) {\n\t\t\ttry {\n\t\t\t\treader = new BufferedReader(new FileReader(new File(fileName)), 32768);\n\t\t\t} catch (Exception ex) {\n\t\t\t\tthrow new NullPointerException(\n\t\t\t\t \"Input file does not exist! Put it in the project folder.\");\n\t\t\t}\n\t\t\ttokenizer = null;\n\t\t}\n\n\t\tpublic String next() {\n\t\t\twhile (tokenizer == null || !tokenizer.hasMoreTokens()) {\n\t\t\t\ttry {\n\t\t\t\t\ttokenizer = new StringTokenizer(reader.readLine());\n\t\t\t\t} catch (IOException e) { throw new RuntimeException(e); }\n\t\t\t}\n\t\t\treturn tokenizer.nextToken();\n\t\t}\n\n\t\tpublic boolean hasNextInt() throws IOException { return reader.ready(); }\n\n\t\tpublic int nextInt() { return Integer.parseInt(next()); }\n\n\t\tpublic double nextDouble() { return Double.parseDouble(next()); }\n\n\t\tpublic long nextLong() { return Long.parseLong(next()); }\n\n\t\tpublic char nextChar() { return next().charAt(0); }\n\n\t\t/**\n\t\t * When you call next(), that entire line will be skipped.\n\t\t * No flushing buffers.\n\t\t * Doesn't work when you want to scan the remaining line.\n\t\t *\n\t\t * @return entire line\n\t\t */\n\n\t\tpublic String nextLine() {\n\t\t\tString str = \"\";\n\t\t\ttry {\n\t\t\t\tstr = reader.readLine();\n\t\t\t\ttokenizer = null;\n\t\t\t} catch (IOException e) { throw new RuntimeException(e); }\n\t\t\treturn str;\n\t\t}\n\t}\n}\n"
 })
 })]
 })]
 })]
 });
}
function MDXContent(props = {}) {
 const {wrapper: MDXLayout} = props.components || ({});
 return MDXLayout ? _jsx(MDXLayout, {
 ...props,
 children: _jsx(_createMdxContent, {
 ...props
 })
 }) : _createMdxContent(props);
}
return {
 frontmatter,
 default: MDXContent
};
function _missingMdxReference(id, component) {
 throw new Error("Expected " + (component ? "component" : "object") + " `" + id + "` to be defined: you likely forgot to import, pass, or provide it.");
}

Table of Contents

Table of Contents

Explanation

Implementation

Join the USACO Forum!