Pythonで蟻本2-5 - グラフ - 競プロはじめました

グラフの問題はよく見るので，ぜひ身につけたいです！

背景：蟻本をやります - 競プロはじめました
テキスト：

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～

作者:秋葉拓哉,岩田陽一,北川宜稔
発売日: 2012/01/28
メディア: Kindle版

【2021.04.24〜05.01】

二部グラフ判定
最短経路問題
- ダイクストラ法
最小全域木
問題

二部グラフ判定

【入力1】
3 3
0 1
0 2
1 2
【出力1】
No

【入力2】
4 4
0 1
0 3
1 2
2 3

【出力2】
Yes (色1：[0, 2]，色2：[1, 3])

【コード】

nv, ne = map(int, input().split())
e = [list(map(int, input().split())) for _ in range(ne)]

g = [[] for _ in range(nv)]
for ei in e:
  g[ei[0]].append(ei[1])
  g[ei[1]].append(ei[0])

color = [0]*nv

# 追加
c1, c2 = [], []

def dfs(v, c):
  """
  頂点vをcで塗り，隣接頂点を調べる
  同じ色ならFalse, 塗られていないなら-cで塗る
  途中Falseを出さずに連結頂点を全て塗れたらTrue
  """
  color[v] = c
  
  # 追加
  if c == 1:
    c1.append(v)
  else:
    c2.append(v)
    
  for vi in g[v]:
    if color[vi] == c:
      return False
    if color[vi] == 0 and not dfs(vi, -c):
      return False
  return True

# 各頂点に対し，塗られていないならdfsを実行する．
# dfsで連結頂点は塗られるので，次のdfsは非連結の頂点
# →塗られていない頂点は好きな色(ここでは1)で塗れば良い
for i in range(nv):
  if color[i] == 0:
    if not dfs(i, 1):
      exit(print('No'))
    
print('Yes (色1：{}，色2：{})'.format(c1, c2))

【ポイント】

グラフを「隣接リスト」で表現します．

最短経路問題

ベルマンフォード法
ダイクストラ法
ワーシャル-フロイド法

ダイクストラ法

関係式「ある頂点の最短距離候補＝隣接頂点の最短距離候補＋頂点間コスト」において，最短距離が確定した隣接頂点だけを扱う方法です．

ヒープを使った方法の補足をします．

queには，更新された(最短距離候補, 頂点)を片っ端から追加していきます．ある頂点が，隣接した複数の頂点から更新を受けた場合，queには同一頂点の情報が複数含まれることになります．

queの最小値を取り出すとき，距離が確定した頂点の情報が出てくる（でないと，「未確定頂点のうち最小距離のものは最短距離を確定できる」ことに反する）ので

最短距離が確定できる，未確定頂点の情報
すでに最短距離が確定した頂点に関する，古い情報

の2通りが考えられます．

同一頂点に関しては，1. のほうが先に取り出されます（最短距離を確定できる情報が先に出てくる）．後から2. が出てきても，1. よりも距離が長いので隣接頂点の距離は更新されません．したがって，2. が出てきた際は更新処理をスキップできます．

最小全域木

プリム法
クラスカル法

問題

Roadblocks

書いてある説明があっさりしすぎていて理解できなかったので，考えてみました．混乱気味な説明です．考察漏れがあるかもしれません．もっと簡単な説明があれば，教えて下さい．

ある頂点のdist2候補は，

隣接頂点のdist候補(※)＋頂点間コスト
隣接頂点のdist2候補(※)＋頂点間コスト

のいずれかです（(※)：キューを使うなら（取り出すときに消してしまうため）確定させる必要がある．）．したがって，(dist候補, 頂点)と(dist2候補, 頂点)をキューに入れ，取り出した頂点の隣接頂点を更新していく処理を考えます．

1. は，ダイクストラ法でキューから取り出したときに捨てていた，最短距離を与える隣接頂点以外から更新を受けた場合の値です．

2. についてはダイクストラ法でキューに入れていなかったので，新たに追加する必要があります．

ダイクストラ法と同じように，キューの最小値から取り出して行きます．もし，(dist2[v]候補, 頂点[v])を取り出したとすると，ダイクストラ法により，この距離より小さいdistをもつ頂点（dist[v]も含まれる）は確定しており，この頂点が1. の方法で更新したdist2[v]はすでにキューに入っています．未確定distをもつ残りの頂点の集合を$X$とすると，$X$に属する頂点のdistは，取り出したdist2[v]候補以上であるため，1. の方法でdist2[v]を更新することはありません．

取り出したdist2[v]候補は未確定dist2の中では最小です．さらに，$X$の頂点が，今後1. の方法でv以外の未確定dist2を更新しても，取り出したdist2[v]候補以上の値にしかなりません．よって，未確定dist2をもつ頂点がdist2[v]を2. の方法で更新することはありません．また，確定dist2をもつ頂点が更新したdist2[v]はすでにキューに入っています．

したがって，未確定の(dist2[v]候補, 頂点[v])をキューから取り出したとき，dist2[v]は確定して良いことがわかります．

【入力】
4 4
1 2 100
2 3 250
2 4 200
3 4 100
【出力】
450

【コード】
参考：Pythonで理解する蟻本「2-5 Roadblocks（POJ No.3255）」(p.102) - クルトンのプログラミング教室

import heapq

N, R = map(int, input().split())

g = [[] for _ in range(N)]
for _ in range(R):
  p1, p2, c = map(int, input().split())
  g[p1-1].append([p2-1, c])
  g[p2-1].append([p1-1, c])

que = []  # [最短距離，頂点]
dist = [float('inf')] * N  # 最短距離
dist2 = [float('inf')] * N  # 2番目の最短距離
dist[0] = 0
heapq.heappush(que, [0, 0])

while len(que) != 0:
  d, v = heapq.heappop(que)  # 最短距離，頂点
  if dist2[v] < d:
    continue
  for w, cost in g[v]:
    d2 = d + cost
    if dist[w] > d2:
      dist[w], d2 = d2, dist[w]
      heapq.heappush(que, [dist[w], w])
    if dist2[w] > d2 and dist[w] < d2:
      dist2[w] = d2
      heapq.heappush(que, [dist2[w], w])
print(dist2[N-1])

【補足】
最短経路を出すのは，whileの前で

prev = [''] * N

値更新時に

prev[w] = v

最後に

path = [N-1]
t = N-1
while t != 0:
  path.append(prev[t])
  t = prev[t]
print('最短経路：', [v+1 for v in reversed(path)])

を追加すればできます．

2番目の最短経路は，上で述べたように，前の2番目の最短経路に頂点を付け足したものとは限らないので，同じ方法ではできません．

Conscription

徴兵した順にグラフを作成していくことを考えます．このとき，辺は2人の関係を利用したことを表すとします．すでに徴兵した人を再度徴兵することはないため，こうしてつくったグラフに閉路はできません．

辺のコストを「(-1)×親密度」と考えれば，与えられた情報を全て含んだ無向グラフから，最小全域木をつくる問題に帰着します．「最終的な答え＝頂点の数×10000＋辺のコスト」となります．

女性を$0,1,...,N-1$で表し，男性を$N, N+1, …, N+M-1$で表します．

注：本書に誤植があります．女がx, 男がyですね．もとの問題：3723 -- Conscription

【入力】
5 5 8
4 3 6831
1 3 4583
0 0 6592
0 1 3063
3 3 4975
1 3 2049
4 2 2104
2 2 781

【出力】
71071

【コード】

N, M, R = map(int, input().split())

es = []
for _ in range(R):
  x, y, c = map(int, input().split())
  es.append([x, N+y, -c])

# UnionFind
class UnionFind:
  # n要素で初期化
  def __init__(self, n):
    self.par = [i for i in range(n)]
    self.rank = [0]*n
    
  # xの根
  def find(self, x):
    if self.par[x] == x:
      return x
    else:
      self.par[x] = self.find(self.par[x])
      return self.par[x]
 
  # xとyの集合を併合(高い木の根に低い木の根を付ける)
  def unite(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x == y:
      return
    if self.rank[x] < self.rank[y]:
      self.par[x] = y
    else:
      self.par[y] = x
      if self.rank[x] == self.rank[y]:
        self.rank[x] += 1

  # 同じ集合か(根が同じか)判定
  def same(self, x, y):
    return self.find(x) == self.find(y)
  
# kruskal
def kruskal():
  es.sort(key=lambda x:x[2])
  uf = UnionFind(N+M)
  res = 0
  for x, y, c in es:
    if not uf.same(x, y):
      uf.unite(x, y)
      res += c
  return res

# 処理
print(10000*(N+M) + kruskal())

特に指定せず「リストのリスト」をソートすると，リスト間の最初の等しくない要素で比較されます．
Pythonで2次元配列（リストのリスト）をソート | note.nkmk.me

なので，コストでソートしたい場合は，コストを最初の要素に持ってくるか，keyで比較に使う関数を指定します．今回は，練習も兼ねてkeyを指定しました．

Layout

不等式をグラフに帰着させる発想は面白いですね．

最短経路問題の解説で現れる不等式

\begin{aligned}
d[i]
&=\min\bigl\{d[j] + \mathrm{cost}(i,j) \,\bigl|\, e=(j,i)\in E \bigr\} \\
&\leq d[j] + \mathrm{cost}(i,j)
\end{aligned}

がポイントです．つまり，

任意の辺$e=(j,i)$について$d[i] \leq d[j] + \mathrm{cost}(i,j)$が成り立ち，
等号$d[i] =d[j] + \mathrm{cost}(i,j)$が成立する辺$e=(j,i)$からなる経路が最短経路となる

ということです．

ここで，

上の不等式は頂点$j$から頂点$i$への経路探索に使われる
最短経路では，全ての不等式で等号が成り立つ

ことに注意して，各頂点$i$への最短経路をたどりながら不等式を追っていきます．すると，各頂点の最短距離を記憶した$\{d[i]\}_{i}$は，不等式を満たす（最短距離とは限らない）他のどんな$\{d^{\prime}[i]\}_{i}$よりも大きいか等しい（$d[i] \geq d^{\prime}[i]$）ことがわかります．よって，$\{d[i]\}_{i}$は不等式を満たすものの中で最大です．

$\{d^{\prime}[i]\}_{i}$の例として，例えば，全ての辺のコストが正なら，全ての$i$で$d^{\prime}[i]=0$というものは，全ての不等式を満たします．

【入力】
4 2 1
1 3 10
2 4 20
2 3 3

【出力】
27 ([0, 7, 10, 27])

【コード】

N, ML, MD = map(int, input().split())

l1, l2 = [], []
for _ in range(ML):
  l1.append(list(map(int, input().split())))
for _ in range(MD):
  l2.append(list(map(int, input().split())))

def update(f, t, c):
  '''
  Bellman–Ford法で繰り返し現れる処理を関数化
  '''
  if f < float('inf') and t > f + c:
    t = f + c
    updated = True
  return t

def bellmanford():
  for _ in range(N):
    updated = False
    # d[i+1] + 0 >= d[i]
    for i in range(N-1):
      d[i] = update(d[i+1], d[i], 0)
    # d[AL] + DL >= d[BL]
    for A, B, D in l1:
      d[B-1] = update(d[A-1], d[B-1], D)
    # d[BD] - DD >= d[AD]
    for A, B, D in l2:
      d[A-1] = update(d[B-1], d[A-1], -D)

# 負閉路チェック
d = [0]*N
bellmanford()
updated = False
if updated:
  exit(print('-1'))

# 負閉路がない場合
d = [float('inf')]*N
d[0] = 0
bellmanford()
if d[N-1] < float('inf'):
  print('{} ({})'.format(d[N-1], d))
else:
  print('-2')

【メモ】本文のkについてのfor は k <= N ではなくて k < N でよいのでは？