CF1499G Graph Coloring 題解

codeforces

luogu

給定一個二分圖，給邊染色。

使得 \(\sum|\text{black}(u)-\text{white}(u)|\) 最小。

其中 \(\text{black}(u)\) 和 \(\text{white}(u)\) 分别表示和 \(u\) 相鄰黑/白邊的數量。

支援動态加邊，查詢哈希值 \(\sum_{e|\text{col}(e)=\text{white}}2^{\text{id}(e)}\bmod 998244353\)，有不超過 \(10\) 次詢問要求查詢哈希值對應的染色方案。

首先考慮一組詢問。

上限顯然是 \(\sum[\deg_i\bmod 2]\)，而我們肯定可以達到這個上界。

具體的，因為是二分圖，是以所有環都是偶環。

我們找到一個偶環，然後相鄰一黑一白染色。

對于所有奇點，我們建一個虛點，讓其向虛點連邊，再删掉虛點。

這樣剩下的一堆鍊肯定構成答案。

考慮怎麼維護這個東西，可以動态維護答案。

插入一條邊隻有以下三種情況

都是鍊的端點：如果顔色相同直接挂，否則需要反轉一整條鍊

一端是一端不是：挂上去

都不是鍊的端點：新增一條鍊

然後直接并查集，支援合并、打tag。

就這個東西寫了一年寫地很屎最後還是調不出來參考了題解的代碼實作。

點選檢視代碼