最小全域木（クラスカル法とUnionFind） - アルゴリズム講習会
最小全域木（クラスカル法とUnionFind） 今回は無向グラフの最小全域木について説明します。 最小全域木を用いる問題はICPCでもたまに出題されます（今年のアジア地区予選東京大会F問題とか）。 最小全域木とは 無向連結グラフの全域木は、グラフが連結であるという条件を保ったまま辺を消去して得られる木のことです。 最小全域木は、全域木を構成する辺のコストの総和が最小となるもののことを指します。 最小全域木問題は、与えられたグラフの最小全域木またはそのコストを求める問題です。 次の図は最小全域木の例です。赤い辺が最小全域木を構成します。 赤い辺以外を消去するとグラフは全域木になり、また少し考えるとこれよりコストの和が小さい全域木が存在しないことがわかります。 最小全域木問題の解法 最小全域木は グラフの辺を、 コストが小さい順に、 閉路を作らないように採用していく という貪欲法で求められます
C++（標準ライブラリの紹介） - アルゴリズム講習会
第2回 C++（標準ライブラリの紹介） 標準ライブラリ（STL）でよく使う機能について紹介します。 ただし書き 以降では聞いたこともないものがたくさん出てきますが、もちろん全て覚える必要はありません stringとvector、ソートは頻出ですが、それ以外のものは簡単な問題では使わなくていいことが多いです 「こんなのがある」ということを覚えてもらい、必要なときにリファレンスを見ながら使えるようになれば十分です string 文字列を扱う。 string str; 空の文字列を宣言 str[i] i番目の文字を参照 str = str2 文字列の代入 str + str2 文字列の連結 str.size() 文字列の長さ str == str2 文字列の比較 str <= str2 str > str2 文字列の辞書順比較 str.find(str2) 文字列の検索（strの中にstr2が見
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
