2025.1.15 鮮花
挖掘機技術哪家強 題解
Bad Apple!!
流れてく 時の中ででも
気だるさが
ほらグルグル廻って
私から 離れる心も 見えないわ
そう知らない?
自分から 動くこともなく
時の隙間に 流され続けて
知らないわ 周りのことなど
私は私 それだけ
夢見てる?
何も見てない?
語るも無駄な 自分の言葉?
悲しむなんて 疲れるだけよ
何も感じず
過ごせばいいの
戸惑う言葉 與えられても
自分の心 ただ上の空
もし私から 動くのならば
すべて変えるのなら 黒にする
こんな自分に 未來はあるの?
こんな世界に 私はいるの?
今切ないの?
今悲しいの?
自分の事も わからないまま
歩むことさえ 疲れるだけよ
人のことなど
知りもしないわ
こんな私も 変われるのなら
もし変われるのなら
白になる?
流れてく 時の中ででも
気だるさがほら
グルグル廻って
私から 離れる心も 見えないわそう
知らない?
自分から 動くこともなく
時の隙間に 流され続けて
知らないわ 周りのことなど
私は私 それだけ
夢見てる?
何も見てない?
語るも無駄な 自分の言葉?
悲しむなんて 疲れるだけよ
何も感じず
過ごせばいいの
戸惑う言葉 與えられても
自分の心 ただ上の空
もし私から 動くのならば
すべて変えるのなら 黒にする
無駄な時間に 未來はあるの?
こんな所に 私はいるの?
私のことを 言えたいならば
言葉にするのなら「ろくでなし」
こんな所に 私はいるの?
こんな時間に 私はいるの?
こんな私も 変われるのなら
もし変われるのなら
白になる?
今夢見てる?
なにも見てない?
語るも無駄な 自分の言葉?
悲しむなんて 疲れるだけよ
何も感じず
過ごせばいいの
戸惑う言葉 與えられても
自分の心 ただ上の空
もし私から 動くのならば
すべて変えるのなら 黒にする
動くのならば
動くのならば
すべて壊すわ
すべて壊すわ
悲しむならば
悲しむならば
私の心 白く変われる?
貴方の事も
私のことも
すべての事も
まだ知らないの
重い目蓋を 開けたのならば
すべて壊すのなら
黒になれ!!!

我記得初一的時候 jijidawang 有一張動圖來著,找不到了。
考慮最大團等于補圖的最大獨立集。
發現依次的 \(a, b, c\) 三點,若 \(a, b\) 不連邊,\(b, c\) 不連邊,則 \(a, c\) 一定不連邊,其對應補圖在按照小的指向大的定向后是個閉包。
于是補圖最大獨立集等于最長反鏈等于最小鏈覆蓋,由于其本身的閉包性質,其可以直接拆點跑二分圖匹配。
具體的,將一個點拆成入點和出點,每次匹配相當于拼接兩個鏈,最后拿 \(n\) 減掉即可。
考慮如何快速匹配。
發現圖十分稠密,相當于是一個競賽圖減掉 \(m\) 條邊,考慮先不退邊跑貪心,考慮若最后余下 \(k\) 個點,則左右兩側的點沒有邊,即至少要斷掉 \(k ^ 2\) 條邊。于是暴力匹配最多 \(\sqrt m\) 個點即可。
具體的,考慮用匹配一個點,用并查集維護每個點的下一個未增廣的點,考慮一個點一定不會被嘗試增廣兩次。判斷是否有邊直接判在原圖上的邊取反即可。
貪心的過程也可以用并查集維護下一個沒有被匹配的點。考慮總共最多只會跳過 \(m\) 次,復雜度是對的。
代碼我沒寫,不放了,可以看 9G 的 QwQ。
P


本文來自博客園,作者:xrlong,轉載請注明原文鏈接:http://www.rzrgm.cn/xrlong/p/18673740
版權聲明:本作品采用 「署名-非商業性使用-相同方式共享 4.0 國際」許可協議(CC BY-NC-SA 4.0) 進行許可。

浙公網安備 33010602011771號