はじめに
俺,グラフが好きだ. 自分の気持ちに嘘はつけない.
俺と,付き合ってくれないか
有名じゃないものでシンプルで面白いものをまとめたい気持ちになった
できること
DAG,ある辺を除いた時にsからtへのパスがまだ存在するかクエリ
なるほど
— SSRS (@SSRS_cp) 2021年9月30日
乱択をしてしまうのが一般的な気がします (トポロジカルソートして、各頂点 v について s から v のパスの個数と v から t のパスの個数を適当な数を法として計算して、
クエリの辺 (v, w) に対し s から t のパスの個数と s から t のパスの個数で辺 (v, w) を使うものの個数が等しければ YES、等しくなければ NO と答えます)
— SSRS (@SSRS_cp) 2021年9月30日
頂点に重み,S-Tパスでxor最大化
これかなり面白かった https://t.co/ywQaNDovoH
— 熨斗袋 (@noshi91) 2020年10月15日
2人で最短路,2人目はコスト無料
3選択肢の燃やす埋めるが出来る時がある
最大流,ある辺を反転したときに流量が増えるか
フロー流して使ってない辺,残余パスでグラフを作る. 終点から逆辺で辿り着ける箇所,始点から辿り着ける箇所を調べておいて,辺を反転させたときにS->Tが到達可能になればそこで流量が増える.
タイトルに書いてないが,流量が全部1じゃないときに同じように解けるのかはあんまり考えてない. 下の問題は流量全部1
https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2594
道に種類があり同一種類なら無料で使い続けられる.(鉄道の運営会社)
今解いています.
普通に解けました.
集約する頂点を作ってやればよいです.別に難しくありませんでした.
鋭意追加をします
シャンプーうめぇ
おわりに
こういうの,先に記事を用意しておいて,出てくるたびに追加するようにしておかないと漏れる