CSES - Download Speed

Authors: Dong Liu, Ahmet Ala

Edit This Page

Time Complexity: O(N⋅M2)\mathcal O(N \cdot M^2)

Just find the max flow of the graph using your favourite max flow algorithm.

C++

The code below uses Edmond Karp's max flow algorithm.

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


long long max_flow(vector<vector<int>> adj, vector<vector<long long>> capacity,
                   int source, int sink) {
	int n = adj.size();
	vector<int> parent(n, -1);


	// Find a way from the source to sink on a path with non-negative capacities
	auto reachable = [&]() -> bool {

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