java - 计算无向图中无序对的数量

Question

可以找到问题的链接 here

Problem Statement

Burger Town is a city that consists of N special junctions and N−1 pathways. There is exactly one shortest path between each pair of junctions. Junction i is located at (xi,yi) and the distance between two junctions i,j is defined by the Taxicab geometry.

Tim has recently afforded a taxicab to work as a taxicab driver. His vehicle was very cheap, but has a very big flaw. It can only drive H units horizontally and V units vertically before refueling.

If a customer wants to be brought from a junction i to another junction j, then this car is only capable of driving the route, iff the sum of horizontal distances and the sum of vertical distances on this path are less than or equal to H and V respectively.

Also, there is a unique path between any two junctions.

Now he has thoughts about returning the vehicle back to the seller. But he first wants to know, if it's even worth it. That's why he wants to know the number of unordered pairs (i,j) such that it is not possible to drive a customer from junction i to junction j.

Constraints

2 ≤ N ≤ 10^5

0 ≤ H,V ≤ 10^14

0 ≤ xi,yi ≤ 10^9

我已经用递归解决了这个问题。但是在某些测试用例中，我的代码超时了。

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        long H = in.nextLong();
        long V = in.nextLong();
        List<Vertex> vertex = new ArrayList<>();

        for (int i=0; i < N; i++) {
            Vertex vx = new Vertex(in.nextLong(), in.nextLong());
            vertex.add(vx);
        }
        for (int i=0; i < N-1; i++) {
            int fromPath = in.nextInt()-1;
            int toPath = in.nextInt()-1;
            vertex.get(fromPath).neighbours.add(vertex.get(toPath));
            vertex.get(toPath).neighbours.add(vertex.get(fromPath));
        }

        long count = 0;

        for (int i=0; i < N; i++) {
            count += (N - findUnorderedPairs(vertex.get(i), null, 0, 0, H, V));
        }

        System.out.println(count/2);
        int temp = 0;

    }

    private static long findUnorderedPairs(Vertex vertex, Vertex previousVertex, long hor, long vert, long H, long V) {
        if (hor > H || vert > V) {
            return 0;
        }

        long result = 1;

        for (Vertex v : vertex.neighbours) {
                result += (v != previousVertex) ? findUnorderedPairs(v, vertex, hor + Math.abs(vertex.x - v.x), vert + Math.abs(vertex.y - v.y), H, V) : 0;

        }

        return result;
    }

    private static class Vertex {
        private long x;
        private long y;
        public ArrayList<Vertex> neighbours;

        public Vertex(long x, long y) {
            this.x = x;
            this.y = y;
            neighbours = new ArrayList<>();
        }
    }
}

我也尝试过 Dijkstras 的实现，但也不走运。

任何关于如何实现更快解决方案的建议都将不胜感激。

Answer 1

这是一个 O(n log^2 n)解决方案(对于这个问题来说它足够快:我成功地使用了它，但我不会在这里发布我的代码，因为我认为理解算法本身比查看它的实现更有用)。

1. 让我们使用树的质心分解。您可以在这里阅读更多相关信息:http://www.ioi2011.or.th/hsc/tasks/solutions/race.pdf .

2. 如何合并子树的解决方案？我们可以将每个点表示为一对 (x, y)其中 x和 y是从这个点到当前根的距离 x和 y轴。对于每个点，我们要计算其他点的数量 x1 + x2 <= H和 y1 + y2 <= W ，或者，换句话说，x1 <= H - x2和 y1 <= W - y2 .因此，固定点的所有“好”点都位于 (0, 0, H - x, W - y) 中。矩形。计算这些点的数量是一个标准问题，可以在 O(n log n) 中解决。使用带有 treap(或坐标压缩和二叉索引树)的扫描线的时间。

3. 这里有一个小问题:我们不应该计算来自同一子树的点。我们可以通过对每个子树运行相同的算法并从答案中减去结果来轻松修复它。

4. 合并步骤在 O(n log n) 中完成时间。因此，总时间复杂度为 O(n log^2 n) .

我知道这个解释不是很详细，但在我看来，使用此处描述的关键思想想出一个完整的解决方案应该不会太困难。