TIOJ 2269：計算機結構
TIOJ 2269 ：計算機結構 題目大意：有一張 $n\leq 2000$ 個點 $m\leq 10^6$ 條邊的無向圖，有 $k\leq 2000$ 種顏色，每條邊有其中一個想要塗的顏色。一開始每條邊都沒有顏色，每次可以選一個簡單環塗一個顏色，若有邊已經有顏色會被蓋過去，問能不能塗成想要的顏色。 解法：倒過來做，維護 $k$ 種顏色邊的生成森林，每次加邊會有兩種情況，第一種是形成一個環，那要把環上的邊都加進 queue，第二種是把兩棵樹接起來，那可以啟發式合併，樹上已經加過的邊可以用並查集跳過，在 queue 裡的邊可以想成變沒有顏色了，所以要把 $k$ 個森林都看過一遍，另外維護一個 dsu，如果一條邊的兩個點 $a,b$ 已經連通，那沒有必要加，因為已經有一條 $a$ 到 $b$ 的路徑被加進去了，時間複雜度 $O(nk\log n+m)$。 $\text{Code：}$ # pragma GCC optimize( "O3,unroll-loops" ) # pragma GCC target( "avx2,popcnt,sse4,abm" ) # include <bits/stdc++.h> using namespace std ; const int N = 2005 ; const int M = 1e6 + 5 ; int n, m, k; bitset <M> vs; queue <tuple< int , int , int >> q; struct DSU { vector < int > to, sz; void init () { to.resize(n + 1 ); sz.resize(n + 1 ); iota(to.begin() + 1 , to.end(), 1 ); fill(sz.begin() + 1 , sz.end(), 1 ); } int dsu ( int x) { return x == to[x] ? x : (to[x] = dsu(to[x]))