問題
既存投稿一覧ページへのリンク
解法手順1
解法アプローチ
- グラフの各頂点に値を割り当てる問題を、差分の制約を満たす問題として捉える。
- 幅優先探索（BFS）を用いて、連結成分ごとに値を割り当てていく。
- 未訪問の頂点から探索を開始し、隣接する頂点に対して差分の制約を満たすように値を割り当てる。
- すべての頂点に値が割り当てられるまで、この処理を繰り返す。
解法手順
- 入力を受け取り、グラフの構造を隣接リストとして保存する。各辺の重みも記録する。
- 各頂点の値を格納する配列と、訪問済みを記録する配列を用意する。
- 未訪問の頂点を見つけたら、その頂点に0を割り当て、BFSのキューに追加する。
- キューから頂点を取り出し、隣接する未訪問の頂点に対して以下の処理を行う：
- 現在の頂点との差分（辺の重み）を考慮して値を割り当てる。
- 割り当てた頂点を訪問済みとしてマークし、キューに追加する。
- キューが空になるまで4の処理を繰り返す。
- すべての頂点が訪問済みになるまで、3-5の処理を繰り返す。
- 最後に、各頂点に割り当てられた値を出力する。
ACコード1
ac.py
from collections import deque
def io_func():
# 頂点数Nと辺数Mを入力として受け取る
N, M = map(int, input().split())
# 辺の情報を格納するリストを初期化
edges = []
for _ in range(M):
# 各辺の情報（始点、終点、重み）を入力として受け取る
u, v, w = map(int, input().split())
edges.append((u-1, v-1, w)) # 0-indexedに調整
return N, M, edges
def solve(N, M, edges):
# 各頂点の値を格納する配列を初期化
ans = [None] * N
# 訪問済みを記録する配列を初期化
visited = [False] * N
# 隣接リストとして辺の情報を格納
cost = [{} for _ in range(N)]
# 辺の情報を隣接リストに変換
for u, v, w in edges:
cost[u][v] = w
cost[v][u] = -w # 逆方向の辺も追加
# すべての頂点を処理
for i in range(N):
if ans[i] is not None:
continue # すでに値が割り当てられている場合はスキップ
# 未訪問の頂点に0を割り当て
ans[i] = 0
visited[i] = True
# 隣接する頂点がない場合はスキップ
if len(cost[i]) == 0:
continue
# BFSのキューを初期化
bfs = deque([(i, v) for v in cost[i].keys()])
for j in cost[i].keys():
visited[j] = True
# BFSを実行
while bfs:
u, v = bfs.popleft()
w = cost[u][v]
# 差分の制約を満たすように値を割り当てる
ans[v] = ans[u] + w
# 隣接する未訪問の頂点をキューに追加
for j in cost[v].keys():
if not visited[j]:
bfs.append((v, j))
visited[j] = True
# 結果を文字列として結合して返す
return " ".join(map(str, ans))
# メイン処理
N, M, edges = io_func()
result = solve(N, M, edges)
print(result)
###
# N: 頂点の数
# M: 辺の数
# edges: 辺の情報を格納するリスト
# ans: 各頂点に割り当てられた値を格納する配列
# visited: 各頂点の訪問状態を記録する配列
# cost: 隣接リストとして辺の情報を格納する辞書のリスト
# bfs: 幅優先探索に使用するキュー
# 1. io_func関数:
# - 標準入力から頂点数N、辺数M、各辺の情報を読み取る
# - 辺の情報を0-indexedに調整して返す
# 2. solve関数:
# - 入力された情報をもとにグラフを構築し、各頂点に値を割り当てる
# - 幅優先探索（BFS）を用いて連結成分ごとに値を割り当てる
# - 未訪問の頂点から探索を開始し、隣接する頂点に差分の制約を満たすように値を割り当てる
# - すべての頂点に値が割り当てられるまで処理を繰り返す
# - 最終的に各頂点に割り当てられた値を文字列として結合して返す
# 3. メイン処理:
# - io_func関数を呼び出して入力を受け取る
# - solve関数を呼び出して問題を解く
# - 結果を標準出力に出力する
オブジェクト指向版1
ac_object.py
from collections import deque
import logging
from abc import ABC, abstractmethod
def setup_logger(debug_mode):
logger = logging.getLogger(__name__)
logger.setLevel(logging.DEBUG if debug_mode else logging.INFO)
formatter = logging.Formatter('%(asctime)s - %(name)s - %(levelname)s - %(message)s')
file_handler = logging.FileHandler('program_trace.log')
file_handler.setFormatter(formatter)
logger.addHandler(file_handler)
return logger
# 入力ハンドラーの抽象クラス
class InputHandler(ABC):
@abstractmethod
def get_input(self):
pass
# 標準入力ハンドラー
class StandardInputHandler(InputHandler):
def get_input(self):
# 頂点数Nと辺数Mを入力として受け取る
N, M = map(int, input().split())
# 辺の情報を格納するリストを初期化
edges = []
for _ in range(M):
# 各辺の情報（始点、終点、重み）を入力として受け取る
u, v, w = map(int, input().split())
edges.append((u-1, v-1, w)) # 0-indexedに調整
return N, M, edges
# 出力ハンドラーの抽象クラス
class OutputHandler(ABC):
@abstractmethod
def output_result(self, result):
pass
# 標準出力ハンドラー
class StandardOutputHandler(OutputHandler):
def output_result(self, result):
print(result)
# グラフソルバー
class GraphSolver:
def __init__(self, debug_mode=False):
self.logger = setup_logger(debug_mode)
def solve(self, N, M, edges):
self.logger.debug(f"グラフソルバーの処理を開始します。N={N}, M={M}, edges={edges}")
# 各頂点の値を格納する配列を初期化
ans = [None] * N
# 訪問済みを記録する配列を初期化
visited = [False] * N
# 隣接リストとして辺の情報を格納
cost = [{} for _ in range(N)]
# 辺の情報を隣接リストに変換
for u, v, w in edges:
cost[u][v] = w
cost[v][u] = -w # 逆方向の辺も追加
self.logger.debug(f"隣接リストの構築が完了しました: {cost}")
# すべての頂点を処理
for i in range(N):
if ans[i] is not None:
self.logger.debug(f"# すでに値が割り当てられている(ans[{i}]=({ans[i]}))場合はスキップ")
continue # すでに値が割り当てられている場合はスキップ
self.logger.debug(f"頂点 {i} の処理を開始します")
# 未訪問の頂点に0を割り当て
ans[i] = 0
visited[i] = True
# 隣接する頂点がない場合はスキップ
if len(cost[i]) == 0:
self.logger.debug(f"頂点 {i} には隣接する頂点がありません")
continue
# BFSのキューを初期化
bfs = deque([(i, v) for v in cost[i].keys()])
for j in cost[i].keys():
visited[j] = True
self.logger.debug(f"BFSキューの初期状態(頂点{i}の隣接点({cost[i].keys()})): {bfs}")
self.logger.debug(f"visitedの状態: {visited}")
# BFSを実行
while bfs:
u, v = bfs.popleft()
w = cost[u][v]
# 差分の制約を満たすように値を割り当てる
ans[v] = ans[u] + w
self.logger.debug(f"頂点 {v} に値 {ans[v]} を割り当てました")
# 隣接する未訪問の頂点をキューに追加
for j in cost[v].keys():
if not visited[j]:
bfs.append((v, j))
visited[j] = True
self.logger.debug(f"頂点 {j} をキューに追加しました")
self.logger.debug(f"すべての頂点の処理が完了しました。結果: {ans}")
# 結果を文字列として結合して返す
return " ".join(map(str, ans))
# メイン処理を行うクラス
class GraphProblemSolver:
def __init__(self, input_handler: InputHandler, output_handler: OutputHandler, solver: GraphSolver):
self.input_handler = input_handler
self.output_handler = output_handler
self.solver = solver
def solve(self):
# 入力を取得
N, M, edges = self.input_handler.get_input()
# 問題を解く
result = self.solver.solve(N, M, edges)
# 結果を出力
self.output_handler.output_result(result)
# メイン処理
if __name__ == "__main__":
input_handler = StandardInputHandler()
output_handler = StandardOutputHandler()
solver = GraphSolver(debug_mode=True) # デバッグモードを有効にする
problem_solver = GraphProblemSolver(input_handler, output_handler, solver)
problem_solver.solve()
オブジェクト図
オブジェクト指向版1で書くメリット
拡張性と再利用性
ac_object.py
class FileInputHandler(InputHandler):
def __init__(self, filename):
self.filename = filename
def get_input(self):
with open(self.filename, 'r') as f:
N, M = map(int, f.readline().split())
edges = []
for _ in range(M):
u, v, w = map(int, f.readline().split())
edges.append((u-1, v-1, w))
return N, M, edges
class FileOutputHandler(OutputHandler):
def __init__(self, filename):
self.filename = filename
def output_result(self, result):
with open(self.filename, 'w') as f:
f.write(result)
# メイン処理を変更
if __name__ == "__main__":
input_handler = FileInputHandler("input.txt")
output_handler = FileOutputHandler("output.txt")
solver = GraphSolver(debug_mode=True)
problem_solver = GraphProblemSolver(input_handler, output_handler, solver)
problem_solver.solve()
テスト容易性
ac_object.py
import unittest
class TestGraphSolver(unittest.TestCase):
def setUp(self):
self.solver = GraphSolver(debug_mode=True)
def test_solve_simple_graph(self):
N, M = 3, 3
edges = [(0, 1, 2), (1, 2, 3), (2, 0, -5)]
result = self.solver.solve(N, M, edges)
self.assertEqual(result, "0 2 5")
def test_solve_disconnected_graph(self):
N, M = 4, 2
edges = [(0, 1, 2), (2, 3, 3)]
result = self.solver.solve(N, M, edges)
self.assertEqual(result, "0 2 0 3")
if __name__ == '__main__':
unittest.main()
独り言
この問題、グラフ問題だと思って問題文を読むと混乱するけど、普通の数学問題だと思って読むと納得行くか。
グラフ問題っぽい出題文は、解き方のヒントってことかな。