孤立点なので、もはや何もしなくても分かります
木幅が2以下のグラフの木分解と動的計画法
なんだこのよくわからんたいとる
卒論を書いているだけだと精神衛生上よくないので, つらくなったときに書いていました.
木幅・木分解についてと, 木分解上で動的計画法をするアルゴリズムについて解説します.
例えば最大独立集合は木幅 として とかで解けます.
また, 一般に木分解を求めるのはヒューリスティックなどをする必要があり最悪ケースを考慮する競プロ的には難しい(難しくなかったら教えてください)ので一般グラフに対する木分解はどこかの記事や本などを読んで頂くこととして, ここでは有用そうな木幅が 以下のグラフの木分解について解説します. ちなみに木幅が 以下のグラフは カクタス, なもりグラフ, 外平面グラフなどの, Series-parallel graph(直並列グラフ) などを含みます. カクタスみたいなのはこどふぉでよくみるかも.
a×b mod 1e9+7
ゆるせね〜〜〜〜〜〜〜
続きを読む最小費用流双対について
わからない
続きを読むKUPC2019参加記
2019/10/13 京都 オンサイト
続きを読む