の呟きは 58
https://dic.nicovideo.jp/a/%E3%82%84%E3%81%A3%E3%81%A6%E3%81%84%E3%81%AA%E3%81%84%E8%A1%8C%E7%82%BA
アラビア数字はインド発祥だと・・・!?アレは今月末か
- (UPD ) #
そういやtsc入れてないな
nodeアプデしたあと手をつけてない・・
今日は金曜日
やる気が無限に消失
まぁ時間の問題だとは思ったけど
1日持たなかったな・・・まぁそもそも
素直にやれば到達可能だから
なんとも細かいとこを詰められるかどうかが鍵
俺はそれが出来ないのでダメ
UFのスニペットって持ってたっけ・・・?
ないね、、、
UF必要ないかも
いあ、ちょっと違うな・・
- (UPD ) #
うーん
辺を消したいんじゃなくて
頂点を消して分割したいんだよね・・・グラフ自体は無向グラフだけど
有向グラフとして扱うこともできるパティーンだし
どっちがいいかは分からんが・・・- (UPD ) #
これ・・・・?
https://ja.wikipedia.org/wiki/%E9%80%A3%E7%B5%90%E3%82%B0%E3%83%A9%E3%83%95#%E7%82%B9%E9%80%A3%E7%B5%90%E5%BA%A6
https://ja.wikipedia.org/wiki/K-%E9%A0%82%E7%82%B9%E9%80%A3%E7%B5%90%E3%82%B0%E3%83%A9%E3%83%95日本語wikipediaでは赤字になってるk点連結成分分解というのがあるらしい・・・
どれ・・・・?
https://en.wikipedia.org/wiki/Category:Graph_connectivity実際に分割する必要はないから
点連結度だけ計算できりゃいい、感じ?
わからん・・・
https://cp-algorithms.com/graph/edge_vertex_connectivity.htmlわからない・・・
どう、すれば
コレの場合、真ん中の1個頂点を消せば分割できるんだけど
最小が1個ではなく2個や3個の場合もあるだろうし
うーん・・・
一番下にある部分が当該の説明なんだろうけど
全ての辺(u,v)を(u2,v1),(v2,u1)に置き換えるの解釈が分からんのだけど・・・
番号の意味は何・・・まるで分からない・・・ボスケテ・・・
点連結度でググって出てくる
どこぞの大学の授業資料でも読み漁るしかないか・・・- (UPD ) #
まだ見つからんけど
最大流だの最小カットだの大学によっては授業で取り扱うのな・・・
俺が通った大学での授業が内容がかなーりしょぼかった可能性・・・?(学生の自主的勉強を求める学風だったらしいし授業の本気度が低いのはそのせいかもしれんが・・・(しかしてレベルの高い大学の授業は資料からして詳しくあるのだから、、、わが大学の授業、酷かった・・・?- (UPD ) #
メンガーの定理とやらで点連結度を求められる理屈ぽいのがあったが
sからtまでの道で頂点を共有しないものの最大数らしいが・・・あー求め方のアイデアっぽいものもこの資料に記載あるな・・・
頂点Aを
他頂点からの流入側頂点A'と他頂点への流出側頂点A''の2つに分裂させてA'からA''の有向辺を作り
他頂点からの流入側頂点A'は容量無限
他頂点への流出側頂点A''も容量無限
A'からA''の有向辺は容量1
として
最大流問題として解いたときに最大流が点連結度になる
と資料に書いてある・・・
すごい
cp-algorithmsとは違うアプローチっぽいけど
この大学資料のやりかた、わかりやすいこのアプローチ
なんか以前にどっかで見たことがあるような
デジャブを感じる・・・
まだ知識もかなり浅かった数年前の自力で解けなかった何かの問題の想定解法の説明とかだったのかもしれない・・・
いあ、わからんけど- (UPD ) #
cp-algorithmsの読み直したら
その大学資料のとほとんど同じ方法だった・・・x1,x2というのがA',A''に相当するやつだった
違いは元のエッジに対する扱いで
大学資料のほうは有向グラフ前提ぽくて
エッジの容量無限としてたけど
cp-algorithmsのほうは容量1で無向グラフっぽい?
まぁ大学生当時にこの資料の大学のレベルの授業されても理解できなかったろうし
落第確定だったから、、、
ゆるい大学だったからこそ俺が卒業できたのだろうけど・・・
shower timeしないと・・・
う、考察不足だた
点連結度を求めるだけじゃダメだった・・・
起点と終点の付近の考察が足りてなかった・・・起点終点の考察入れたのに
まだダメだ・・・つかそもそも
組んだやつが正しいか怪しいundirected graph vertex connectivity
わからん・・・
偶然的にでたらめなやつが少し当たりだったらしいが全部ではない・・・
やはり1つだけ通らぬ・・・
何が足りてないんだ・・・
わからん・・・
寝る
変異株について発見の国名を併記するニュース記事が減りつつあるようだ・・・
- (UPD ) #
WHOの方針に従った(権威に屈した)のか
あるいはWHOの考え方に会社として賛同して合わせたのか
単なる記者次第の表記ゆれなのか (omitted)
神奈川2000人超えた・・・と?