Home » 国际竞赛 » Details

USACO 2022 February Contest, Gold Problem 3. Moo Network

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

USACO 2022 February Contest, Gold Problem 3. Moo Network

Farmer John's

N

cows (

1 \leq N \leq 10^{5}

) are spread far apart on his farm and would like to build a communication network so they can more easily exchange electronic text messages (all of which of course contain variations of "moo").

The $i$ th cow is located at a distinct location $(x_{i}, y_{i})$ where $0 \leq x_{i} \leq 10^{6}$ and $0 \leq y_{i} \leq 10$ . The cost of building a communication link between cows $i$ and $j$ is the squared distance between them: $(x_{i} - x_{j})^{2} + (y_{i} - y_{j})^{2}$ .

Please calculate the minimum cost required to build a communication network across which all the cows can communicate. Two cows can communicate if they are directly connected by a link, or if there is a sequence of links along which their message can travel.

**Note: the time limit for this problem is 4s, twice the default.**

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

The first line of input contains $N$ , and the next $N$ lines each describe the $x$ and $y$ coordinates of a cow, all integers.

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

Please output the minimum cost of a network that will allow all cows to communicate. Note that this cost might be too large to fit into a 32-bit integer and may require use of 64-bit integers (e.g., "long long" integers in C++).

SAMPLE INPUT:

SAMPLE OUTPUT:

SCORING:

Test cases 2-3 satisfy $N \leq 1000$ .
Test cases 4-15 satisfy no additional constraints.

Problem credits: Brian Dean

USACO 2022 February Contest, Gold Problem 3. Moo Network 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Richard Qi, Benjamin Qi)

Let the cows be nodes of a graph, where an edge is between every pair of cows with weight equal to the squared distance between them. Our goal is to find a Minimum Spanning Tree of this graph.

Partial Credit: Because there are a total of $O (N^{2})$ edges, we can run Kruskal's or Prim's to solve this task in $O (N^{2} \log N)$ or $O (N^{2})$ . A few modifications to the code from the Moocast analysis suffice.

Nick Wu's code:

import java.io.*;
import java.util.*;
public class MooNetworkSlow {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
		int n = Integer.parseInt(br.readLine());
		int[] x = new int[n];
		int[] y = new int[n];
		for(int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			x[i] = Integer.parseInt(st.nextToken());
			y[i] = Integer.parseInt(st.nextToken());
		}
		parent = new int[n];
		ArrayList<Edge> edges = new ArrayList<Edge>();
		for(int i = 0; i < n; i++) {
			parent[i] = i;
			for(int j = 0; j < i; j++) {
				long distance = (long)(x[i] - x[j]) * (x[i] - x[j]) + (long)(y[i] - y[j]) * (y[i] - y[j]);
				edges.add(new Edge(i, j, distance));
			}
		}
		Collections.sort(edges);
		long sumWeights = 0;
		int numComponents = n;
		for(Edge curr: edges) {
			if(find(curr.i) != find(curr.j)) {
				merge(curr.i, curr.j);
				sumWeights += curr.w;
				if(--numComponents == 1) {
					break;
				}
			}
		}
		pw.println(sumWeights);
		pw.close();
	}
	
	static int[] parent;
	public static int find(int curr) {
		return parent[curr] == curr ? curr : (parent[curr] = find(parent[curr]));
	}
	
	public static void merge(int x, int y) {
		parent[find(x)] = find(y);
	}
	
	static class Edge implements Comparable<Edge> {
		public int i, j;
		public long w;
		public Edge(int a, int b, long c){
			i=a;
			j=b;
			w=c;
		}
		public int compareTo(Edge e) {
			return Long.signum(w-e.w);
		}
	}
	
}

Full Credit: The main idea is to reduce the number of edges we need to consider to $O (N)$ , using the special condition that $0 \leq y_{i} \leq 10$ .

We use this important fact: consider $3$ nodes of a graph $a$ , $b$ , $c$ . Suppose that the weights of the three edges between these nodes satisfies $w_{b c} < w_{a b}$ and $w_{a c} < w_{a b}$ . Then, the minimum spanning tree can be chosen such that edge $a b$ is not present. This can be proven by analyzing Kruskal's algorithm: the algorithm first encounters $b c$ and $a c$ in the sort order, immediately after which $a$ and $b$ must be connected. So, when $a b$ is encountered, $a$ and $b$ are already connected.

Now, given points $a = (x_{1}, y_{1}), c = (x_{2}, y_{2}), b = (x_{3}, y_{3})$ such that $x_{1} \leq x_{2} < x_{3}$ and $y_{2} = y_{3},$ we don't need to consider the edge between $(x_{1}, y_{1})$ and $(x_{3}, y_{3})$ because of the reason above. Specifically, we can easily show that $w_{b c} < w_{a b}$ and $w_{a c} < w_{a b}$ .

Now, suppose that for each point $(x_{1}, y_{1})$ we want to generate all the edges to points $(x_{2}, y_{2})$ where $x_{1} \leq x_{2}$ which could possibly be part of a MST. Consider the points in order of decreasing $x .$ By the above observation, we only need to consider the edges from $(x_{1}, y_{1})$ to the last added point for each $0 \leq y \leq 10$ , which can be maintained in linear time using an array of size $11$ . Thus, we only need to run Kruskal on $11 N$ distinct edges.

The overall time complexity of running this algorithm is $O ((N max y_{i}) (\log N + \log max y_{i}))$ , which comes from sorting the edge weights during Kruskal.

Danny Mittal's code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class MooNetwork {
    static int[] union;
 
    static int find(int u) {
        if (union[union[u]] != union[u]) {
            union[u] = find(union[u]);
        }
        return union[u];
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        TreeMap<Integer, Integer>[] rows = new TreeMap[11];
        for (int y = 0; y <= 10; y++) {
            rows[y] = new TreeMap<>();
        }
        int[] xs = new int[n];
        int[] ys = new int[n];
        for (int j = 0; j < n; j++) {
            StringTokenizer tokenizer = new StringTokenizer(in.readLine());
            xs[j] = Integer.parseInt(tokenizer.nextToken());
            ys[j] = Integer.parseInt(tokenizer.nextToken());
            rows[ys[j]].put(xs[j], j);
        }
        List<Edge> edges = new ArrayList<>();
        for (int j = 0; j < n; j++) {
            for (int y = 0; y <= 10; y++) {
                Map.Entry<Integer, Integer> entry = y == ys[j] ? rows[y].lowerEntry(xs[j]) : rows[y].floorEntry(xs[j]);
                if (entry != null) {
                    long dx = xs[j] - entry.getKey();
                    long dy = ys[j] - y;
                    edges.add(new Edge(j, entry.getValue(), (dx * dx) + (dy * dy)));
                }
            }
        }
        union = new int[n];
        for (int j = 0; j < n; j++) {
            union[j] = j;
        }
        edges.sort(Comparator.comparingLong(edge -> edge.weight));
        long answer = 0;
        for (Edge edge : edges) {
            int u = find(edge.a);
            int v = find(edge.b);
            if (v != u) {
                union[v] = u;
                answer += edge.weight;
            }
        }
        System.out.println(answer);
    }
 
    static class Edge {
        final int a;
        final int b;
        final long weight;
 
        Edge(int a, int b, long weight) {
            this.a = a;
            this.b = b;
            this.weight = weight;
        }
 
        @Override
        public String toString() {
            return "Edge{" +
                    "a=" + a +
                    ", b=" + b +
                    ", weight=" + weight +
                    '}';
        }
    }
}

Fun Fact #1: Note that Squared Euclidean Distance was not very special in our proof. In particular, the same solution can be used for Manhattan Distance or regular Euclidean Distance.

Fun Fact #2: Note that finding an MST in Squared Euclidean Distance is equivalent to finding an MST in Euclidean Distance, although it is not equivalent to finding an MST in Manhattan distance (can you see why?). So, an algorithm that can find a Euclidean MST could be used to solve this problem. General Euclidean MST (without the bound on $y_{i}$ ) can be done in $O (N \log N)$ time.