Codeforces 892E(最小生成树+可撤销并查集+离线)

Codeforces 892D
题意:给出一个$n$个点$m$条边的无向联通图,有$q$个询问每个询问询问一个边集$E_i$,回答这些边能否在同一个最小生成树中

本题又加强我对最小生成树定理的理解……

首先同一个图最小生成树所有相同边权数量都是一样的,并且在 Kruskal 加边时不同边互相之间独立。也就是说我们可以将每个边权分开来加,并且每种边权都可以被一条不产生环的。关于更多最小生成树的定理,请看Bzoj 1016
其实这题和Bzoj 1016有类似的地方。
我们将询问离线。按照边权大小从小到大加边。枚举当前边权大小为$w$, 如果在某个询问中有$w$大的边,那么就将这些$w$大的边权加到并查集里看会不会产生环,如果产生环则无解,当然这些边要撤销,用能撤销的并查集。然后每次循环完以后,将当前边权的所有边加入并查集不撤销,继续做。

1、最小生成树的定理要掌握:1切割性质、2回路性质、3相同边权数量相等,4不同边权加入时互相独立,5不产生环的同权值边可以替换边
2、调试大代码要用分块调试和输出调试,并且要运用解释数组方法来检查

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<stack>
#include<set>
#include<queue>
#include<climits>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair

using namespace std;

namespace flyinthesky {  

    const int MAXN = 500000 + 5;

    struct edge {
        int u, v, w;
        bool operator < (const edge &b) const {return w < b.w;} 
    } ed[MAXN], ed2[MAXN];
    struct whw {int id, fr, t;}; // id:是哪个询问的。fr,t:在输入边排序后(que)的index范围 
    struct ask {
        int id; // 输入边编号
        bool operator < (const ask &b) const {return ed[id].w < ed[b.id].w;} 
    };

    int n, m, q, ans[MAXN], maxw = 0, f[MAXN], sz[MAXN];
    vector<whw > a[MAXN]; // a[权值][index] = 询问中边权为 权值 的边(whw类型)
    vector<ask > que[MAXN]; // que[输入边index][index] = 输入边排序后边编号(ask类型) 
    stack<pair<int, int > > s;

    int find(int x) {return x == f[x] ? x : find(f[x]);} //no compress
    void mg(int a, int b) {
        int x = a, y = b;
        if (sz[x] > sz[y]) swap(x, y);
        f[x] = y, sz[y] += sz[x], s.push(mp(x, y));
    }
    void cc(int tms) {
        while (tms-- && !s.empty()) {
            pair<int, int > p = s.top(); s.pop();
            int x = p.fir, y = p.sec;
            f[x] = x, sz[y] -= sz[x];
        }
    }

    void clean() {
        ms(ans, 0);
    }
    int solve() {
        cin >> n >> m; 
        clean();
        for (int i = 1; i <= m; ++i) scanf("%d%d%d", &ed[i].u, &ed[i].v, &ed[i].w), maxw = max(maxw, ed[i].w), ed2[i] = ed[i];
        sort(ed2 + 1, ed2 + 1 + m);
        cin >> q;
        for (int i = 1; i <= q; ++i) {
            int Ki; scanf("%d", &Ki);
            for (int x, j = 1; j <= Ki; ++j) scanf("%d", &x), que[i].push_back((ask){x});
            sort(que[i].begin(), que[i].end());
            int lst = 0;
            for (int j = 1; j < (int)que[i].size(); ++j) {
                int id = que[i][j].id, lid = que[i][j - 1].id;
                if (ed[id].w != ed[lid].w) {
                    a[ed[lid].w].push_back((whw){i, lst, j - 1});
                    lst = j;
                }
            }
            a[ ed[ que[i][ (int)que[i].size() - 1 ].id ].w ].push_back((whw){i, lst, (int)que[i].size() - 1});
        }
        for (int i = 0; i <= n; ++i) f[i] = i, sz[i] = 1;
        int now = 1;
        for (int i = 1; i <= maxw; ++i) {
            for (int j = 0; j < (int)a[i].size(); ++j) {
                int fl = 0, tms = 0;
                whw &ct = a[i][j];
                for (int k = ct.fr; k <= ct.t; ++k) {
                    edge &e = ed[que[ct.id][k].id];
                    int x = find(e.u), y = find(e.v);
                    if (x == y) {fl = 1; break;} else mg(x, y), ++tms;
                }
                if (fl) ans[ct.id] = 1; //no
                cc(tms);
            }
            while (ed2[now].w == i) {
                int x = find(ed2[now].u), y = find(ed2[now].v);
                if (x != y) mg(x, y);
                ++now;
            }
        }
        for (int i = 1; i <= q; ++i) printf("%s", ans[i] == 1 ? "NO\n" : "YES\n");
        return 0; 
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
------ 本文结束 ------