日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。
問１０７「最短ネットワーク」
以下の無向ネットワークは7つの頂点と重み付きの12個の辺からなり, 重みの総和は243である.
このネットワークを以下の行列で表現することができる.
| A | B | C | D | E | F | G | |
| A | - | 16 | 12 | 21 | - | - | - |
| B | 16 | - | - | 17 | 20 | - | - |
| C | 12 | - | - | 28 | - | 31 | - |
| D | 21 | 17 | 28 | - | 18 | 19 | 23 |
| E | - | 20 | - | 18 | - | - | 11 |
| F | - | - | 31 | 19 | - | - | 27 |
| G | - | - | - | 23 | 11 | 27 | - |
しかし, このネットワークを, 全ての頂点が連結であるように適当な辺を除いた上で最適化することが出来る. 節約される量が最大化されるように取り除いたネットワークが以下の画像である. この場合, 辺の重みの総和は93であり, 元のネットワークからの節約量は 243 - 93 = 150 である.
6Kバイトのテキストファイル network.txt (右クリックして保存すること) には40頂点のネットワークを行列表示したものが記されている. ネットワーク全体が連結であるが冗長な辺を取り除いたときの節約量を最大にするようにした場合の節約量を答えよ.
注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。
私の回答例は以下の通りです。
def f(sIn):
pIn = open(sIn)
L0 = pIn.read().replace("\n", ",").split(",")
pIn.close()
pIn = None
n = int(len(L0)**.5)
L1, a = [], 0
for i, w in enumerate(L0):
if not w.isdigit(): continue
w, (y, x) = int(w), divmod(i, n)
if x<y:
L1.append((w, (x, y)))
a += w
c, V, E = 0, [i for i in xrange(n)], []
for w, (v1, v2) in sorted(L1):
if V[v1]!=V[v2]:
c += w
E.append(((v1, v2),w))
minv, maxv = min(V[v1], V[v2]), max(V[v1], V[v2])
for i,s in enumerate(V):
if s==maxv: V[i] = minv
if not sum(V): break
return a-c, a, c, E
s = "p107_network.csv"
sIn = os.path.join(os.path.dirname(__file__), s)
s, a, c, E = f(sIn)
print "saving:", s
print "all :", a
print "cut :", c
print "edge:", E
問題文では「冗長な辺を取り除いて」とありますが、重い辺を順に除外していくと、重い辺の代わりに軽い辺を複数除外する方が全体として軽くなる場合に、重い辺の除外を解除しなくてはいけなくなり、ロジックが複雑になります。
そこで、軽い辺を順に採用していくことにします。
ただし、辺を１つ採用するごとに新しくつながる頂点または頂点群が増えることが条件です。
これを全頂点を網羅するまで続けます。
頂点または頂点群が増えるかどうかの判定は、各頂点ごとにつながっている最小頂点番号で判定します。
最初は自分だけなので、各頂点とも最小頂点番号に自分自身の頂点番号を設定します。
そして、重みの軽い辺から順にその両端点の最小頂点番号が異なる場合に採用し、両端点の最小頂点番号も洗い直しておきます。
すべての頂点の最小頂点番号が0になれば終了です。
最大頂点番号でも同様のことが可能ですが、終了判定がわかりやすいので最小頂点番号を使用します。
また、辺には向きが無いので、頂点番号の小さい方から大きい方への辺のみ使用します。
１．関数f(sIn)
ネットワーク情報のcsvファイルを入力し、
重みの節約数、重みの合計、カット後の重み合計、採用する辺のリストを返します。
・L0は:入力ファイルのcsv区切りのリストです。
改行文字と半角カンマで区切ってリストにします。
・変数nは頂点数です。
リストL0は各頂点を行列表示しているので、頂点数nはリストL0の平方根になります。
・リストL1は辺のリストです。
(重み、（頂点番号１、頂点番号２）)のタプルをためます。
ただし、重みは数値で、頂点番号１＜頂点番号２の場合に限ります。
・aは重みの総合計です。
・wは重み、xは列番号、yは行番号です。
リストL0は行列表示を一次配列にしているので、
その通し番号iを頂点数nで割った商が行番号y、余りが列番号xになります。
divmod関数で商と余りを一度に求めています。
・リストVは最小頂点番号のリストです。
V[i]は頂点iがつながっている最小頂点番号です。
初期値は各頂点の自分自身の頂点番号です。
・リストEは採用した辺のリストです。
・辺のリストL1をソートして１つずつ処理します。
ソートキーは未指定の場合は最初の要素なので、この場合、重みに軽い順になります。
・v1、v2は辺の両端の頂点番号です。
このそれぞれのつながっている最小頂点番号が異なる場合、
まだつながっていない頂点または頂点群なので、辺を採用します。
・minv, maxvは、採用した辺の両端点がそれぞれつながっている最小頂点番号の
小さい方と大きい方です。
最小頂点番号リストVで、値がこの小さい方の場合、大きい方の値に洗いなおします。
・最後に、最小頂点番号リストVの全要素の和をチェックし、この和が0ならば全頂点から0番目の頂点につながったということになるので処理終了です。
解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
saving: 259679
all : 261832
cut : 2153
edge: [((21, 36), 1), ((27, 34), 6), ((10, 33), 7), ((28, 34), 9), ((13, 39), 17), ((4, 35), 19), ((9, 29), 25), ((5, 25), 27), ((20, 28), 27), ((3, 9), 32), ((5, 34), 33), ((7, 9), 35), ((8, 15), 36), ((9, 13), 36), ((29, 37), 36), ((11, 17), 41), ((6, 10), 42), ((2, 9), 47), ((28, 37), 48), ((9, 10), 50), ((8, 24), 53), ((10, 19), 53), ((5, 36), 54), ((0, 31), 56), ((5, 23), 66), ((12, 29), 68), ((15, 31), 68), ((16, 18), 73), ((3, 38), 76), ((20, 30), 80), ((22, 28), 83),((14, 26), 89), ((35, 36), 91), ((1, 37), 102), ((26, 32), 102), ((11, 21), 104), ((2, 26), 108), ((1, 16), 122), ((0, 18), 131)]
