Home » 国际竞赛 » Details

USACO 2021 December Contest, Silver Problem 2. Connecting Two Barns

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月5日下午2:36

USACO 2021 December Contest, Silver Problem 2. Connecting Two Barns

Farmer John's farm consists of a set of $N$ fields $(1 \leq N \leq 10^{5})$ , conveniently numbered $1 \dots N$ . Between these fields are $M$ bi-directed paths $(0 \leq M \leq 10^{5})$ , each connecting a pair of fields.

The farm contains two barns, one in field 1 and the other in field $N$ . Farmer John would like to ensure that there is a way to walk between the two barns along some series of paths. He is willing to build up to two new paths to accomplish this goal. Due to the way the fields are situated, the cost of building a new path between fields $i$ and $j$ is $(i - j)^{2}$ .

Please help Farmer John determine the minimum cost needed such that barns $1$ and $N$ become reachable from each-other.

INPUT FORMAT (input arrives from the terminal / stdin):

Each input test case contains $T$ sub-cases ( $1 \leq T \leq 20$ ), all of which must be solved correctly to solve the input case.The first line of input contains $T$ , after which $T$ sub-test cases follow.

Each sub-test case starts with two integers, $N$ and $M$ . Next, $M$ lines follow, each one containing two integers $i$ and $j$ , indicating a path between two different fields $i$ and $j$ . It is guaranteed that there is at most one path between any two fields, and that the sum of $N + M$ over all sub-test cases is at most $5 \cdot 10^{5}$ .

OUTPUT FORMAT (print output to the terminal / stdout):

Output $T$ lines. The $i$ th line should contain a single integer giving the minimum cost for the $i$ th sub-test case.

SAMPLE INPUT:

SAMPLE OUTPUT:

2
1

In the first sub-test case, it is optimal to connect fields 2 and 3 with a path, and fields 3 and 4 with a path.

In the second sub-test case, it is optimal to connect fields 3 and 4 with a path. No second path is needed.

SCORING:

Test case 2 satisfies $N \leq 20$ .
Test cases 3-5 satisfy $N \leq 10^{3}$ .
Test cases 6-10 satisfy no additional constraints.

Problem credits: Nick Wu

USACO 2021 December Contest, Silver Problem 2. Connecting Two Barns 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Nick Wu)

To solve the first subtask, we can brute force all possible pairs of edges to add. This solution has complexity $O (N^{4} (N + M))$ .

To solve the second subtask, we need to be more disciplined in what edges we consider adding. We can start by computing the connected components of the barns - that is, maximal collections of barns where one can reach any barn from any other barn in the collection.

There are therefore two cases to consider here. We can either add an edge from the connected component containing barn 1 to the connected component containing barn $N$ , or we pick an intermediate connected component, add one edge from it to the connected component containing barn $1$ , and add another edge from it to the connected component containing barn $N$ .

This observation on its own only reduces the number of pairs of edges to consider in the worst case by a constant factor. However, we now have two independent instances of the same subproblem to solve - given two connected components, what is the minimum cost needed to connect them with a single edge?

We can naively brute force this for all pairs of components we care about, for an $O (N^{2})$ algorithm.

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

using namespace std;

void dfs(const vector<vector<int>>& edges, vector<int>& component, const int currv, const int id) {
  for(int child: edges[currv]) {
    if(component[child] != id) {
      component[child] = id;
      dfs(edges, component, child, id);
    }
  }
}

void solve() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> edges(n);
  for(int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    edges[a].push_back(b);
    edges[b].push_back(a);
  }
  vector<int> component(n);
  iota(component.begin(), component.end(), 0);
  for(int i = 0; i < n; i++) {
    if(component[i] == i) {
      dfs(edges, component, i, i);
    }
  }
  if(component[0] == component[n-1]) {
    cout << "0\n";
    return;
  }
  vector<vector<int>> componentToVertices(n);
  for(int i = 0; i < n; i++) {
    componentToVertices[component[i]].push_back(i);
  }
  long long ans = 1e18;
  vector<long long> srccost(n, 1e9);
  vector<long long> dstcost(n, 1e9);
  for(int i: componentToVertices[component[0]]) {
    for(int j = 0; j < n; j++) {
      srccost[component[j]] = min(srccost[component[j]], (long long)abs(i - j));
    }
  }
  for(int i: componentToVertices[component[n-1]]) {
    for(int j = 0; j < n; j++) {
      dstcost[component[j]] = min(dstcost[component[j]], (long long)abs(i - j));
    }
  }
  for(int i = 0; i < n; i++) ans = min(ans, srccost[i]*srccost[i] + dstcost[i]*dstcost[i]);
  cout << ans << "\n";
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t;
  cin >> t;
  for(int i = 0; i < t; i++) {
    solve();
  }
  return 0;
}

To optimize this to $O (M + N)$ time, we have to take advantage of the cost function.

For a given barn and a given connected component we want to connect it to, we only care about the smallest integer in the connected component greater than it, as well as the largest integer in the component less than it.

There are a couple ways to find these integers. One way would be to use binary search. It is also possible to do this in linear time by maintaining the pair of indices we consider and considering adding edges from vertex $i$ in increasing order of $i$ . The pair of indices we consider will be nondecreasing, so we only consider a linear number of edges.

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
 
using namespace std;
 
void dfs(const vector<vector<int>>& edges, vector<int>& component, const int currv, const int id) {
  for(int child: edges[currv]) {
    if(component[child] != id) {
      component[child] = id;
      dfs(edges, component, child, id);
    }
  }
}
 
void solve() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> edges(n);
  for(int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    edges[a].push_back(b);
    edges[b].push_back(a);
  }
  vector<int> component(n);
  iota(component.begin(), component.end(), 0);
  for(int i = 0; i < n; i++) {
    if(component[i] == i) {
      dfs(edges, component, i, i);
    }
  }
  if(component[0] == component[n-1]) {
    cout << "0\n";
    return;
  }
  vector<vector<int>> componentToVertices(n);
  for(int i = 0; i < n; i++) {
    componentToVertices[component[i]].push_back(i);
  }
  long long ans = 1e18;
  vector<long long> srccost(n, 1e9);
  vector<long long> dstcost(n, 1e9);
  int srcidx = 0;
  int dstidx = 0;
  for(int i = 0; i < n; i++) {
    while(srcidx < componentToVertices[component[0]].size()) {
      srccost[component[i]] = min(srccost[component[i]], (long long)abs(i - componentToVertices[component[0]][srcidx]));
      if(componentToVertices[component[0]][srcidx] < i) srcidx++;
      else break;
    }
    if(srcidx) srcidx--;
    while(dstidx < componentToVertices[component[n-1]].size()) {
      dstcost[component[i]] = min(dstcost[component[i]], (long long)abs(i - componentToVertices[component[n-1]][dstidx]));
      if(componentToVertices[component[n-1]][dstidx] < i) dstidx++;
      else break;
    }
    if(dstidx) dstidx--;
  }
  for(int i = 0; i < n; i++) ans = min(ans, srccost[i]*srccost[i] + dstcost[i]*dstcost[i]);
  cout << ans << "\n";
}
 
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t;
  cin >> t;
  for(int i = 0; i < t; i++) {
    solve();
  }
  return 0;
}

[/hide]