各種アルゴリズムの C++ による実装
ACM/ICPC（プログラミングコンテスト）系列の問題を解くことを目標にして，各種アルゴリズムを C++ で実装してみた．極めて意地が悪い類の問題には対応していないし，特定の入力に対して高速に動くということもない．計算量も最良とは限らない．
これらを参考にする方への注意とお願い：
- これらの記述は正確とは限りません．参考文献を参照することを強く推奨します．間違っている場合は是非教えてください．
- これらのプログラムは間違っているかもしれません．各人で検証することを強く推奨します．バグがあれば是非教えてください．
- 分類が怪しいので，これはこっちだろう，ということがあればコメントを下さると助かります．
注意！
現在書き換え中
TODO
- 分類を正しく行う．
- 全体的に説明と使い方を詳しく．
- Verify していないものを Verify．
- ボロノイ図（いつになることやら……）
基本
グラフ
- 基本要素
- 連結成分
- 最短路
- 全域木
- フロー・カット
- マッチング
- ツリー
- 周遊路
- その他
平面幾何
空間幾何
データ構造
文字列
- 基本操作
- 文字列検索
- 文字列検索その他
- 文字列系データ構造
- 文字列処理その他
ソート
数理
- 整数
- 素数
- 法演算
- 数論的関数
- 有理数
- 行列演算
- 最適化
- その他
典型動的計画法
典型バックトラック
その他
探索
- 深さ優先探索
- 幅優先探索
- 両側探索
- A^* 探索
- 反復深化
謝辞
以下のチームのライブラリを大いに参考にさせていただきました．本当にありがとうございました．
参考文献
- M. Berg, O. Schwartzkopf, M. Kreveld, M. Overmars, "Computational Geometry Algorithms and Applications", Springer-Verlag
- M. Shamos, F. Preparata, "Computational Geometry - An Introduction", Springer Verlag
- T. Cormen, C. Leiserson, R. Rivest, C. Stein, "Introduction to Algorithms, Second Edition", MIT Press
- B. Korte, B. Vygen, "Combinatorial Optimization: Theory and Algorithms", Springer-Verlag
- R. Sedgewick, "Algorithms in C", Addison-Wesley
- 石畑 清，"アルゴリズムとデータ構造"，岩波書店
- S. Skiena, M. Revilla, "Programming Challenges", Springer-Verlag
- J. Kleinberg, E. Tardos, "Algorithm Design", Addison Wesley