USACO 2016 February Contest, Gold Problem 3. Fenced In

Category: 计算机国际竞赛 Date: 2017年11月9日上午10:37

原题下载

USACO2016-FEB-G3

答案

(Analysis by Nathan Pinsker)

For this problem, we're given a grid and want to connect all the interiors to each other. If we think of each interior region as a point and add edges between points representing the length of the fence that separates them, then this problem becomes one of finding a minimum spanning tree on a graph. Since our graph has $O (n * m)$ vertices and each vertex has at most 4 edges, it also has $O (n * m)$ edges, meaning that we can simply run our favorite minimum spanning tree algorithm to solve the problem.

However, we can actually make this solution even faster! If you're interested, see the platinum version of this problem.

Here is Mark Gordon's code, with an implementation of Kruskal's algorithm:

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

using namespace std;

int A, B, N, M;

int nd(int r, int c) {
  return r * M + c;
}

int P[2010*2010];

int find(int x) {
  return x == P[x] ? x : P[x] = find(P[x]);
}

bool merge(int x, int y) {
  int X = find(x);
  int Y = find(y);
  if (X == Y) return false;
  P[X] = P[Y] = P[x] = P[y] = rand() % 2 ? X : Y;
  return true;
}

int main() {
  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++;

  for (int i = 0; i < N * M; i++) {
    P[i] = i;
  }

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

  return 0;
}

以上就是关于【USACO 2016 February Contest, Gold Problem 3. Fenced In】的解答，如需了解学校/赛事/课程动态，可至翰林教育官网获取更多信息。

往期文章阅读推荐：

USACO计算机奥赛如何认证成绩？2026赛季黄金铂金组“定时开赛”规则详解！

USACO计算机奥赛考试语言是什么？C++、Python、Java选哪个效率最高？