APIO 2017 - Traveling Merchant

Author: Andi Qu

First, find the maximum profit of each footpath by comparing the buying and selling prices of the endpoints for each of the KK items. We now have a directed graph where each edge has a profit pp and a time to traverse tt.

Ratios are inconvenient, so let's consider a simpler problem: given RR, can we find a profit cycle with profit PP and time TT such that P/TRP/T \geq R?

This is convenient because we can make it linear: this problem is equivalent to checking whether we can find a profit cycle with profit PP and time TT such that PTR0P - TR \geq 0. If we weight each edge as ptRp - tR, this is equivalent to checking whether a non-negative cycle exists in the graph.

Since RR is good if R+1R + 1 is good, we can binary search for the largest good RR. We can then use Floyd-Warshall to check whether there is a negative cycle.

(For a similar problem, see Cruise from BkOI 2016. Beware though - it's geometry!)


#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;
const ll INF = LLONG_MAX / 2;
int n, m, x;
ll b[101][1001], s[101][1001];
ll graph[101][101], profit[101][101], graph2[101][101];

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!