4

给定一个简单的无向图，其中包含 N 个顶点，编号为 1 到 N，每个顶点包含一个来自 {1,2,..7} 的数字。从带有空字符串 S 的顶点 1 开始，我们穿过一些顶点（没有限制）到达顶点 N。对于途中的每个顶点，我们将相应的数字添加到字符串 S 的右侧。最后我们得到S 作为十进制整数。要求你找到一个满足 S 可以被它的所有数字整除的方式，并且 S 的数字之和必须尽可能小。

输入

有几个测试用例（最多十五个），每个组成如下：

The first line contains a positive integer N (N ≤ 100).
The second line contains N digits (separated by spaces), the i-th digit is the value of the i-th vertex.
N last lines, each contains N values of {0, 1} (separated by spaces), the j-th value of the i-th line is equal to 1 if there is an edge connecting two vertices (i, j), otherwise 0.

输入以 N = 0 结束。

输出

对于每个测试用例，在一行上输出找到的最小数字总和，如果没有解决方案，则输出 -1。

例子

输入：4

1 2 1 4

0 1 1 1

1 0 0 1

1 0 0 1

1 1 1 0

输出：7

请指导我

可能存在自循环和循环，因此可以访问节点 1 和节点 N 任意次数

4

3 回答 3

2

如果将给定图转换为不允许循环的其他图，则可以使用Dijkstra 算法解决此问题。

为此，让我们从字符串被 7 整除开始。看看这个序列：1、10、100，...（mod 7）。由于 7 是素数，由于费马小定理，10 7-1 = 1 (mod 7) 。这意味着 1, 10, 100, ... (mod 7) 序列是周期性的，周期为 6。这将用于转换图形，这也允许使用 S n -1 ( mod 7): S n = S n-1 + 10 n%6 * n_th_digit (mod 7)。

有必要从节点 N 开始最短路径搜索，因为该路径可能在转换图的几个节点之一处结束。这也允许快速确定（使用路径的前 2 个节点）是否允许访问节点“5”、节点“4”和其他“偶数”节点。

算法的开放集（优先级队列）应该包含优先级本身（数字总和），只要 3 个附加位和 3 个余数：允许“4”、“3”访问、“7”访问S % 3、、、S % 7和S.length % 6。

图形应转换如下。每个顶点扩展为 3 个顶点，一个只允许用于S%3==0，其他 - 用于S%3==1和S%3==2。然后将每个顶点扩展为 7（对于S%7），然后将每个顶点扩展为 6（对于S.length % 6）。可以将所有这些扩展拟合到原始图：只需向每个节点添加一个 3D 数组（大小为 3*7*6）的反向指针。在搜索最短路径时，非空反向指针确定算法的闭集（它们不允许循环）。当找到最短路径时，反向指针允许重建该路径中的节点序列。找到最短路径的时刻是通过访问节点 1 来确定的(node_3_not_visited || S%3==0) && (node_7_not_visited || S%7==0)。

于 2012-05-10T08:52:33.993 回答
0

首先在数学上找到集合中给定数字的 LCM。

让我解释一下场景....给定一组数字...找到LCM，然后以这样一种方式遍历vetices，使得它们的路径产生数字。由于它的LCM，它是总和为最小值的数字

对于集合 {0,1,2,3,4} LCM 是 12 所以从 1 遍历到 2 集合 {0,1,2,3,4,5,6,7} LCM 是 420 ..（我想我是的）

于 2012-05-08T05:00:17.203 回答
0

使用A*搜索算法，其中“成本”是数字的总和，可除性决定了您可以遍历哪些边。

于 2012-05-09T19:56:51.240 回答