USACO Gold 2019 December - Milk Pumping

Authors: Qi Wang, Ryan Chou, George Pong

Edit This Page

Official Analysis (C++)

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.

Implementation

Time Complexity: O(M2log⁡N+MN)\mathcal{O}(M^2 \log N + MN)

C++

#include <bits/stdc++.h>
using namespace std;


struct Edge {
	int v, c, fl;
};


int n, m;
const int PRECISION = 1e6;
vector<vector<Edge>> adj;

Python

import heapq


with open("pump.in", "r") as infile:
	n, m = map(int, infile.readline().split())


	graph = [[] for _ in range(n)]
	flow_rates = []


	for _ in range(m):
		a, b, c, f = map(int, infile.readline().split())

Java

Time Complexity: O(Mlog⁡N+N)\mathcal{O}(M \log N + N)

// Created by Qi Wang
import java.io.*;
import java.util.*;


public class pump {
	static int N;
	static int M;
	static List<Node>[] adjList;
	static boolean[] vist;
	static int[] costs;

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum