USACO 2016 February Contest, Platinum Problem 2. Fenced In

原题下载

USACO2016-FEB-P2

答案

(Analysis by Nathan Pinsker)

This problem can be thought of as finding the minimum spanning tree on an (n+1)×(m+1)(n+1)×(m+1) grid of vertices representing the interiors of each region. Unfortunately, this number can be rather large, and so this naive approach won't quite work. However, we can take the ideas of minimum spanning tree algorithms and apply it to this problem. The most naturally applicable algorithm would be Kruskal's algorithm, since it doesn't require us to keep track of a large amount of state at once.

Kruskal's algorithm has us start by adding the edge of least weight -- but, due to the way this problem is structured, there are probably going to be many such edges all in the same row or column of the grid. In other words, once we find this edge, we might as well move all those edges in that row or column. We can process the tree in O(n+m)O(n+m) blocks, "opening up" a column or row all at once. Note that at each step, every row and column we've dealt with so far should be connected to every other row and column. Also, if we're connecting a row and have already connected kk columns (for k > 1), then we only need to remove m−km−k fences in that row, since the columns we've already processed are guaranteed to be connected. This gives a fairly straightforward algorithm: we process the fences in order of their thickness, removing as many segments as we need to to connect the fence to every other fence we've processed so far. This gives an O(n+m)O(n+m) algorithm after sorting the input.

Another way to think about this problem is to note that, if we have an optimal solution, then the solution isn't affected by switching two adjacent rows or two adjacent columns. (This is because the connectivity within those two rows or two columns can be flipped without changing the cost to connect to the surrounding area.) Thus, we can sort the rows and columns in increasing order of how thick they are, which makes reasoning about connectivity significantly easier.

Mark Gordon uses this idea in his solution below:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
  int A, B, N, M;
  cin >> A >> B >> N >> M;

  vector<int> VA(N + 1), HA(M + 1);
  for (int i = 0; i < N; i++) {
    cin >> VA[i];
  }
  for (int j = 0; j < M; j++) {
    cin >> HA[j];
  }

  sort(VA.begin(), VA.end());
  for (int i = 0; i < N; i++) {
    VA[i] = VA[i + 1] - VA[i];
  }
  VA[N] = B - VA[N];

  sort(HA.begin(), HA.end());
  for (int i = 0; i < M; i++) {
    HA[i] = HA[i + 1] - HA[i];
  }
  HA[M] = A - HA[M];

  sort(VA.begin(), VA.end());
  sort(HA.begin(), HA.end());
  N++; M++;

  long long result = 1ll * VA[0] * (M - 1) +
                     1ll * HA[0] * (N - 1);
  for (int vi = 1, hi = 1; vi < N && hi < M; ) {
    if (VA[vi] < HA[hi]) {
      result += VA[vi++] * (M - hi);
    } else {
      result += HA[hi++] * (N - vi);
    }
  }
  cout << result << endl;

  return 0;
}