問題 http://uva.onlinejudge.org/external/108/10858.html意訳 生物名が複数種与えられる。与えられた関係から食物連鎖に関わるグループを部類分けできるので、そのときの食物連鎖のグループの最大サイズを出力せよ。ただしAがBを捕食する関係にあるとき、…

解法 拡張ダイクストラ。各エッジをわたるコストが0または1で、1のみではないことを考えると幅優先ではなくコストの小さいものをキューから取り出す拡張ダイクストラがいいと思うけど、多分幅優先でも出来る。問題では場外から目的地に向かうが、スタート地…

問題概要 ある有向グラフが与えられる。このグラフをたどるとき、そのパスの数が多項式の距離で表されるかどうか判定せよ。一度通ったノードでもパスがあれば何度でも通ることが出来る。解法 i から到達できる j を全て探す。中継点kを決めるN^3の方式で、判…