3

有一个 N × N 的方形网状网格线，如下图所示。网格的节点位于点 (X, Y)，其中 X 和 Y 是从 0 到 N-1 的整数。电流流过电网，在 (0, 0) 和 (N-1, N-1) 的节点之间。 在此处输入图像描述

最初，所有电线都传导电流，但电线以每秒一根的速度烧毁。烧坏由三个零索引的整数数组 A、B 和 C 来描述，每个数组的大小为 M。对于每个时刻 T (0 ≤ T < M)，在第 T 秒内，节点之间的连线 (A[T ]、B[T]) 和：

    (A[T], B[T] + 1), if C[T] = 0 or
    (A[T] + 1, B[T]), if C[T] = 1

烧坏了。您可以假设这些数组描述了现有的电线，并且没有电线烧毁超过一次。你的任务是确定电流何时停止在 (0,0) 和 (N-1,N-1) 的节点之间流动。

写一个函数：

int wire_burnouts(int N, int A[], int M, int B[], int M2, int C[], int M3);

即，给定整数 N 和数组 A、B 和 C，返回电流在 (0, 0) 和 (N-1, N-1) 的节点之间停止流动的秒数。如果即使在所有 M 根电线烧坏后电流仍继续流动，则该函数应返回 -1。

例如，给定 N = 4、M = 9 和以下数组：

A[0] = 0 B [0] = 0 C[0] = 0
A 1 = 1 B 1 = 1 C 1 = 1
A 2 = 1 B 2 = 1 C 2 = 0
A[3] = 2 B [ 3] = 1 C[3] = 0
A[4] = 3 B [4] = 2 C[4] = 0
A[5] = 2 B [5] = 2 C[5] = 1
A[6] = 1 B [6] = 3 C[6] = 1
A[7] = 0 B [7] = 1 C[7] = 0
A[8] = 0 B [8] = 0 C[8] = 1

您的函数应该返回 8，因为就在第八根线烧断之后，(0, 0) 和 (N-1, N-1) 处的节点之间没有连接。这种情况如下图所示：

在此处输入图像描述

给定 N = 4、M = 1 和以下数组：

A[0] = 0 B [0] = 0 C[0] = 0

您的函数应该返回 -1，因为烧断单根线不会破坏 (0, 0) 和 (N-1, N-1) 处的节点之间的连接。

假使，假设：

    N is an integer within the range [1..400];
    M is an integer within the range [0..2*N*(N−1)];
    each element of array A is an integer within the range [0..N−1];
    each element of array B is an integer within the range [0..N−1];
    each element of array C is an integer within the range [0..1].

复杂：

    expected worst-case time complexity is O(N2*log(N));
    expected worst-case space complexity is O(N2), beyond input storage (not counting the storage required for input arguments).
4

1 回答 1

5

构建完整的电线网格。然后销毁第一条 M/2 线。使用深度优先搜索检查连通性。如果仍然连接，则再销毁 M/4 根电线。如果没有，请恢复 M/4 最近损坏的电线。继续这个二分搜索，直到找到合适的 T。

时间复杂度取决于深度优先搜索的次数：O(log M) <= O(log N) 和每个深度优先搜索的复杂度：O(N 2 )。

使用不相交集数据结构可以改善以前的结果。

构建完整的电线网格。然后按照数组 A、B 和 C 的指示销毁 M 条线。将网格的剩余连接组件添加到不相交集数据结构中。

然后依次恢复连线，从这些数组的最后一个元素开始，一直到它们的第一个元素。这样做时，找到剩余在不相交集结构中的集合的并集。当包含节点 (0, 0) 和 (N-1, N-1) 的集合连接在一起时停止。

如果不相交集数据结构使用秩并集和路径压缩方法，则整个算法的时间复杂度为 O(N 2 α(N))，其中 α 是反阿克曼函数。这实际上与 O(N 2 ) 一样好。

如果我们使用与原始网格线对偶的图，则可能会改善先前的结果：对偶图的节点对应于原始图的面，对偶图的每条边与原始图的对应边相交。将需要两个额外的节点：节点 L 连接到对偶图的每个顶部和左侧节点，节点 R 连接到每个底部和右侧节点。

                                                    对偶图

如果此对偶图包含从 L 到 R 的路径，则节点 (0, 0) 和 (N-1, N-1) 无法相互连接。如果没有从 L 到 R 的路径，则节点 (0, 0) 和 (N-1, N-1) 是连接的。

最初对偶图是完全断开的。在从原始图中删除边的同时，我们将相应的边添加到对偶图中。同时我们更新了不相交集数据结构。一旦包含节点 L 和 R 的集合连接在一起，就停止。

该算法只需要访问其输入数组 A、B 和 C 的元素一次，这使其成为在线算法。

时间复杂度的最大限制因素现在是对偶图节点数组的初始化时间：O(N 2 )。如果有办法避免这种初始化，我们会得到渐近更有效的 O(M α(M)) 算法。初始化问题有几种方法：

  • 使用这个技巧在 O(1) 时间内初始化数组。这给出了 O(M α(M)) 最坏情况时间算法。但在实践中，几乎不可能在不初始化内存的情况下分配内存（出于安全原因）。
  • 初始化数组一次，然后多次使用该算法。这给出了 O(M α(M)) 摊销时间算法。
  • 使用哈希表存储对偶图的节点。这给出了 O(M α(M)) 的预期时间算法。这也将空间复杂度提高到 O(M)。
于 2012-12-07T19:27:50.453 回答