Gorillas和Poles会合点算法 - 无法找出完美的解决方案和失败的测试用例

Question

我在竞争激烈的编码网站上练习时遇到了这个问题.在经过深思熟虑后,我提到了下面提到的逻辑,但不知何故,我无法通过大多数测试用例.此外,该网站没有透露测试用例,所以我对可能出现的问题一无所知.问题描述如下:

问题陈述

一群大猩猩在马戏团中表演,并且位于多个杆上.两极将其基部浸入水中.您将获得2-D平面中所有极点的x和y坐标.由于大猩猩不会游泳,所以他们从一个极移到另一个极的唯一方法就是跳跃.然而,当一只大猩猩从一个杆跳到另一个杆时,他跳下的杆被深深地淹没了1个单位.请注意,只有被跳下的杆才会被淹没.被跳到的杆不受影响.对于马戏团的高潮,所有大猩猩必须在一个杆上相遇.所有大猩猩的跳跃能力即"J"都给你.跳跃能力只不过是一次跳跃中大猩猩可以覆盖的距离.只有当A和B之间的几何距离小于或等于"J"即跳跃能力时,大猩猩才能从极A跳到B. 每根杆子都有一个高于水面的给定高度,因此固定数量的大猩猩可以从每个杆上跳下,之后它会被淹没.如果极点从0到N-1编号,则需要确定在马戏团高潮期间所有大猩猩可能遇到的极点.假设大猩猩可以在4极中的所有杆上相遇,则打印0 1 2 3.如果它们只能在0和4极上相遇,则打印0 4.如果它们无法在任何杆上相遇,则打印-1.根据上述条件,大猩猩可以进行任意数量的跳跃.

输入

第一行是整数N,表示极数.
第二行是十进制J,表示所有大猩猩的跳跃能力.

连续的N条线包括:
xi =极点的x坐标,yi =极点的y坐标,gi =极点上的大猩猩的初始数量,hi =最初在水面上的极点的高度.

产量

打印大猩猩可能遇到的两极的序列号.如果他们无法在任何地方见面,请打印-1.

约束

1 <= N <= 100

0 <= J <= 100000

-10000 <= xi,yi <= 10000

0 <= gi <= 25

1 <= hi <= 200

样本测试案例

输入

3 30.0
1 10 5 20
5 10 5 20
8 10 5 20

产量

0 1 2

说明

所有杆之间的距离<30.0,因此当距离时,所有大猩猩都可以跳任何杆到任何其他杆.此外,所有杆的高度即20>否.在每个杆上都有大猩猩,所以大猩猩可以通过直接跳跃它们轻松地在0号,1号或2号杆上相遇.

途径

让我们存储2-D整数数组中给出的所有信息.

// 4 columns to store xi, yi, gi and hi for each given pole.
int [][] polesInfo = new int[N][4];

首先,我们需要一个循环来逐个遍历所有极点,看看来自所有极点的大猩猩是否可以在我们正在看的一个极点上跳跃.

boolean [][] result = new boolean[N];
for(int i = 0; i < N; i++) {
    result[i] = canAllGorillasJumpToI(polesInfo,i)
}

在方法canAllGorillasJumpToI()中,我基于3个案例实现了它,

1. 所有大猩猩都可以直接跳到Pole i即所有杆都有足够的高度,所有杆都位于小于J的距离.因此可以从所有杆直接跳跃,就像给定的测试案例一样,我们返回true.

2. 其中一个杆比其高度有更多的大猩猩,并且所有大猩猩都不可能从它跳到任何地方,因此最终会留下一些大猩猩,在这种情况下,所有大猩猩都无法在第i个杆处遇到,因此返回假.

3. 这是我遇到的最复杂的案例,并怀疑我错过了什么.如果一些大猩猩由于它们的杆距离很远而无法直接跳跃,请检查其他可能的跳杆是否具有足够的容量,然后在可能的情况下连续跳转到目标杆.

1和2很简单.但这是我的逻辑3.

存储所有大猩猩不能在ArrayList中直接跳转的所有极点.总结需要间接跳跃的大猩猩数量.

for (Integer p : poles) {
    gorillaPositions += polesInfo [p][2];
}

找到目标极点附近的所有极点,即在小于J的距离内.存储其可用剩余容量的总和.

//pseudocode
if (poles in vicinity) {
    capacity += polesInfo [i][3] - polesInfo [i][2];
}

最后,我正在检查gorilla posiitons> = capacity并返回true.

if (gorillaPositions >= capacity ) {
    return true;
}

在某些情况下,这种逻辑似乎有效,但大多数测试用例都失败了.我知道在案例3中有些事情是不对的,我无法想到这种情况.

什么是更好的算法呢？我应该使用图表吗？任何帮助或测试用例将不胜感激.如有必要,我可以分享更多细节或测试用例.

Answer 1

该问题可以建模为具有顶点容量的最大流问题。

首先构建图，其中顶点是极点，边缘是大猩猩可以在其之间跳跃的极点对。所有这些边缘在两个方向上都具有无限（或非常大）的容量。每个顶点的容量等于可以从该极点跳跃的大猩猩的数量。

在此网络中，向每个极点添加一个带有弧的源顶点，其容量等于从该顶点开始的大猩猩数量。依次对于每个可能的交汇点，添加一个汇点，该汇点具有从每个无限容量的极点顶点开始的弧线。如果从源到汇的价值流等于大猩猩的数量，那么大猩猩就可以聚集在那个极点。

要将顶点容量转换为弧容量，请将每个有容量的顶点拆分为两个顶点。所有传入的弧线都会到达两个弧线之一；所有传出弧线均从另一弧线离开。从第一个顶点到第二个顶点，添加一条容量等于顶点容量的弧。