library for graph
dijkstra.hpp
非負辺グラフに対する1点始点最短経路問題
- dijkstra method
verify: AOJ(Single Source Shortest Path)
bellman_ford.hpp
グラフに対する1点始点最短経路問題(非負もOK), 閉路検出.
- bellman ford method
verify: AOJ(Single Source Shortest Path(Negative Edges))
warshall_floyd.hpp
グラフに対する全点対最短経路問題, 閉路検出(d[i][i]<0なら閉路)
- warshall floyd method
verify: AOJ(All Pairs Shortest Path)
ford_fulkerson.hpp
最大流, 最小カット問題
- Ford Fulkerson method
verify: AOJ(Maximum Flow)
bipartile.hpp
グラフが2部グラフか判定する
- check bipartile
- maximum matching
verify: AOJ(Bipartile Matching)
topological_dag.hpp
トポロジカルソート
- topological sort
verify: AOJ(Topological Sort)
prim.hpp
最小全域木(木を拡張していく)
- Minimum Spanning Tree (Prim)
verify: AOJ(Minimum Spanning Tree)
kruskal.hpp
最小全域木(最小コストの辺から見ていく)
- Minimum Spanning Tree (Kruskal)
verify: AOJ(Minimum Spanning Tree)
boruvka.hpp
最小全域木(森を連結していく)
- Minimum Spanning Tree (Boruvka)
verify: AOJ(Minimum Spanning Tree)
edmonds_karp.hpp
最大流アルゴリズム(最短路から更新していく)
- Maximum Flow
verify: AOJ(Maximum Flow)
dinic.hpp
最大流アルゴリズム(BFS+DFS)
- Maximum Flow
verify: AOJ(Maximum Flow)
primal_dual.hpp
最小費用流アルゴリズム(最短路を構築していく. ポテンシャルを導入してdijkstraを使う)
- Minimum Cost Flow
verify: AOJ(Minimum Cost Flow)
successive_shortest_path.hpp
最小費用流アルゴリズム(最短路を構築していく. ベルマンフォードを使う)
- Minimum Cost Flow
verify: AOJ(Minimum Cost Flow)
strongly_connected_componens.hpp
強連結成分分解
2-SATは全clauseが2つの論理式のORとなっているもののみ
- kosaraju
verify: AOJ(Strongly Connected Components) - two satisfiability
hopcroft_karp.hpp
二部マッチング
- hopcroft_karp
verify: AOJ(Bipartile Matching)
steiner_tree.hpp
最小シュタイナー木
- steiner tree
verify: yukicoder(遠い未来)
verify: AOJ(Problem F: Chocolate with Heart Marks)
lowlink.hpp
lowlinkを用いてグラフの橋, 関節点などを求める.
- lowlink
verify: AOJ(Articulation Points)
verify: AOJ(Bridges) - two edge connected components