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]));
    }
    inline bool merge(int a, int b) {
        a = dsu(a), b = dsu(b);
        if (a == b) return 0;
        if (sz[a] < sz[b]) swap(a, b);
        to[b] = a;
        sz[a] += sz[b];
        return 1;
    }
} Dsu;

struct DSU2 {
    vector<int> to;
    void init() {
        to.resize(n + 1);
        iota(to.begin() + 1, to.end(), 1);
    }
    int dsu(int x) {
        return x == to[x] ? x : (to[x] = dsu(to[x]));
    }
    inline void merge(int a, int b) {
        a = dsu(a), b = dsu(b);
        if (a == b) return;
        to[b] = a;
    }
};

struct Tree {
    vector<tuple<int, int, int>> e;
    vector<vector<pair<int, int>>> adj;
    vector<int> pa, pid, h;
    DSU dsu;
    DSU2 dsu2;
    void init() {
        e.clear();
        adj = vector<vector<pair<int, int>>>(n + 1, vector<pair<int, int>>());
        dsu.init();
        dsu2.init();
        pa = pid = h = vector<int>(n + 1, 0);
    }
    void dfs(int pos) {
        for (auto &[np, id] : adj[pos]) if (np != pa[pos]) {
            h[np] = h[pos] + 1;
            pa[np] = pos;
            pid[np] = id;
            dsu2.to[np] = (vs[id] ? dsu2.to[pos] : np);
            dfs(np);
        }
    }
    void build() {
        for (auto &[a, b, i] : e) {
            if (dsu.merge(a, b)) {
                adj[a].emplace_back(b, i);
                adj[b].emplace_back(a, i);
            } else {
                vs[i] = 1;
                q.emplace(a, b, i);
            }
        }
        for (int i = 1; i <= n; i++) if (h[i] == 0) {
            h[i] = 1;
            dfs(i);
        }
    }
    inline void add(int a, int b, int id) {
        if (dsu.dsu(a) != dsu.dsu(b)) {
            if (dsu.sz[dsu.dsu(a)] < dsu.sz[dsu.dsu(b)]) swap(a, b);
            dsu.merge(a, b);
            adj[a].emplace_back(b, id);
            adj[b].emplace_back(a, id);
            h[b] = h[a] + 1;
            pa[b] = a;
            pid[b] = id;
            dsu2.to[b] = a;
            dfs(b);
            return;
        }
        a = dsu2.dsu(a);
        b = dsu2.dsu(b);
        while (a != b) {
            if (h[a] < h[b]) swap(a, b);
            if (vs[pid[a]] == 0) {
                vs[pid[a]] = 1;
                q.emplace(a, pa[a], pid[a]);
            }
            dsu2.merge(pa[a], a);
            a = dsu2.dsu(a);
        }
    }
} tree[N];

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int tt;
    cin >> tt;
    while (tt--) {
        cin >> n >> m >> k;
        for (int i = 1; i <= k; i++) tree[i].init();
        for (int i = 1; i <= m; i++) {
            int a, b, c;
            cin >> a >> b >> c;
            vs[i] = 0;
            tree[c].e.emplace_back(a, b, i);
        }
        for (int i = 1; i <= k; i++) tree[i].build();
        Dsu.init();
        int cnt = 0;
        while (q.size()) {
            auto [a, b, id] = q.front();
            q.pop();
            cnt++;
            if (Dsu.merge(a, b) == 0) continue;
            for (int i = 1; i <= k; i++) tree[i].add(a, b, id);
        }
        cout << (m == cnt ? "Yes\n" : "No\n");
    }
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！