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 items. We now have a directed graph where each edge has a profit and a time to traverse .
Ratios are inconvenient, so let's consider a simpler problem: given , can we find a profit cycle with profit and time such that ?
This is convenient because we can make it linear: this problem is equivalent to checking whether we can find a profit cycle with profit and time such that . If we weight each edge as , this is equivalent to checking whether a non-negative cycle exists in the graph.
Since is good if is good, we can binary search for the largest good . 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, s;ll graph, profit, graph2;
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!