计算无方向图中无序对的数量

Question

可以在此处找到问题的链接

问题陈述

汉堡镇是一个由N个特殊路口和N-1路径组成的城市.每对交叉点之间只有一条最短路径.交叉点i位于(xi,yi),并且两个交叉点i,j之间的距离由出租车几何形状定义.

蒂姆最近提供了一辆出租车作为出租车司机.他的车很便宜,但有很大的缺陷.在加油前,它只能水平驱动H单位,垂直V单位.

如果客户想要从交叉口i带到另一个交叉路口j,那么这辆车只能驱动路线,如果水平距离和这条路径上的垂直距离之和小于或等于H,分别为V.

此外,任何两个交叉点之间都有一条独特的路径.

现在他想到将车辆还给卖家.但他首先想知道,如果它甚至值得.这就是为什么他想知道无序对(i,j)的数量,这样就不可能将客户从交叉点i驱动到交叉点j.

约束

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)。

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