4

1 から N までの番号が付けられた N 個の頂点を含む単純な無向グラフがあり、各頂点には {1,2,..7} の数字が含まれています。空の文字列 S を持つ頂点 1 から始めて、頂点 N までいくつかの頂点 (制限なし) を移動します。途中の頂点ごとに、文字列 S の右側にそれぞれの数字を追加します。 10 進整数としての S。S がすべての桁で割り切れ、S の桁の和ができるだけ小さくなるようにする方法を見つけてください。

入力

いくつかのテスト ケース (最大 15 個) があり、それぞれ次のように形成されます。

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 行に出力するか、解がない場合は -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

与えられたグラフが、サイクルが許可されていない別のグラフに変換される場合、この問題はダイクストラのアルゴリズムで解決できます。

これを行うには、文字列を 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 から最短パスの検索を開始する必要があります。また、これにより、ノード「5」、ノード「4」、およびその他の「偶数」ノードへのアクセスが許可されているかどうかを (パスの最初の 2 つのノードを使用して) すばやく判断できます。

アルゴリズムのオープン セット (プライオリティ キュー) には、3 つの追加ビットと 3 つの剰余がある限り、プライオリティ自体 (数字の合計) が含まれている必要がS % 3ありS % 7ますS.length % 6。

グラフは次のように変換する必要があります。各頂点は 3 つの頂点に拡張されます。1 つは のみに許可され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

「コスト」が数字の合計であるA*検索アルゴリズムを使用し、割り切れる可能性によって、どのエッジを通過できるかが決まります。

于 2012-05-09T19:56:51.240 に答える
0

最初に、セットで指定された数値の LCM を数学的に見つけます。

シナリオを言い換えると....一連の数値が与えられます... LCMを見つけて、パスが数値になるようにveticesをトラバースします.LCMであるため、合計が最小になる数値です

セット {0,1,2,3,4} の LCM は 12 であるため、セット {0,1,2,3,4,5,6,7} の 1 から 2 までのトラバースの LCM は 420 です。私は正しい）

于 2012-05-08T05:00:17.203 に答える