グラフ理論
サンプルコード とりあえず、今まで書いたことを元にそのままコードを書いてみることにする。それなりに読める形で1100byte強。これを最終的に250byteほどに短縮するわけだが、このままではどう考えても不可能だ。基本的なアルゴリズムは変えずに、まずデー…
探索イメージ
ラベリング
基本アルゴリズム
http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1011 長さがバラバラの棒の切れ端をつなぎ合わせて、同じ長さの棒を作る問題。つなぎ合わせた棒の長さは考えられる答えの中で最小でなければならない。なるべく短くするということは、同じ長さの…
隣接行列だって無駄が多いじゃないか〜! はい。その通りです。しかしプログラマーの皆さんは、この程度事なんか全然気にしないのです。余裕のぷっぷくぷーで解決解決。
前回「隣接行列は扱い易いしヨロシイわよ」と書いたので、接続行列ってヤツはもういらないんじゃないかという気がしてきたのだが、否。断じてイナゾウ。武士の道は接続行列。・・・すんません疲れてます(´ω`)
今回は隣接行列に絞って書く。というのも、この隣接行列というのは色々とアレンジしやすい。
「グラフ」と言っても、前回のような単純なものばかりではない。たとえばこんなグラフはどうだろう。
第1回といえば用語の整理とグラフの定義と相場が決まっているのだが、そんなのはちょろっと調べればすぐにわかるし書いてるうちに飽きてしまいそうなので、最初に出てきたときに説明することにします。
グラフ理論って結構流行ってるのか、googleなんかで調べるとたくさん出てくる。 なので、グラフ理論そのものについてあーだこーだ書いたところで何にも面白くないのだ。じゃあ何を書くかってことになるのだが、これはもちろんプログラマの、プログラマによる…