Young Zeff's Blog: USACO Training Problem: Cow Tours

Young Zeff's Blog: USACO Training Problem: Cow Tours

Here's an interesting graph theory problem:
http://cerberus.delos.com:790/usacoprob2?a=osacVNAncMv&S=cowtour

What makes this problem hard is the incorrect assumption that many people (including me) make.

The first part is relatively simple. The idea is to calculate the Euclidean distances between connected vertices and store these distances in a matrix. Even though the problem gives that vertex i is not connected to itself, we can assume it is with no harm. Thus, dist(i,i) = 0 for all i.

The next step is to use Floyd-Warshall on the matrix of distances such that for each i,j, dist(i,j) stores the shortest path from vertex i to vertex j. dist(i,j) is infinity if j is unreachable from i.

Make an array of size n that stores the farthest distance that can be traveled from a given vertex taking only shortest paths (not counting infinity). Thus farthest[i]=max_not_infinity(dist[i]).

It is advantageous but not necessary to find the diameter of each field by precalculation.

Keep track of a global variable that has initial value infinity.
Finally loop through the entire matrix, and every time dist(i,j)==infinity (which means that edge(i,j) does not exist and is a candidate to be filled in), find the maximum of the following values:
d1 - farthest[i]+distance(P_i,P_j)+farthest[j]
d2 - max(diameter[i],diameter[j])  //This is the part that most people forget
where distance(Point a, Point b) returns the Euclidean distance between two points and where P_i and P_j denote the two points that are connected by edge (i,j).
Now update the global variable if max(d1,d2) < current value of global variable.

*If you are getting an error on test case 7 or higher, it is probably because you overlooked the value d2, and to see why it is necessary consider the test case (from TopCoder):

Read full article from Young Zeff's Blog: USACO Training Problem: Cow Tours