[UOJ 14][UER #1]DZY Loves Graph

danihao123 posted @ 2018年9月02日 13:24 in 题解 with tags uoj 并查集 , 1144 阅读
转载请注明出处:http://danihao123.is-programmer.com/

一张\(n\)个点的图,初始没边,然后要求你支持以下操作:

  • 给定\((x, y)\),在\(x\)和\(y\)两点间添加一条长度为\(i\)的边(假设这是第\(i\)次操作)。
  • 给定\(k\),删除当前图中边权最大的\(k\)条边。
  • 撤销上一次操作。保证存在上一次操作且不是撤销操作。

共\(m\)次操作,每次操作后输出当前图最小生成树的边权和(不存在的话输出\(0\))。

\(1\leq n\leq 300000, 1\leq m\leq 500000\)。

一开始往可持久化XXX上想,脑袋炸了……虽然好像也能做?

假如说只有加边和删边操作,那怎么做呢?注意到后面的边一定不会有前面的边优,所以加进来的边如果能减小当前最小生成森林的联通块数,那就加上这条边。删除操作的话,注意到一条在最小生成森林中的边如果被删除了那么在前面不会有边来替代它的作用,所以删除的时候就需要撤销在并查集中的合并操作就行了,因此我们用栈来维护当前按时间顺序加进来的所有边对并查集的影响,删除的时候撤销就行。可撤销并查集也很好实现,写一个只用启发式合并不用路径压缩的并查集就行了。

不过撤销操作有一些毒瘤呢……其实也好做,如果说上一次是加边操作的话那么这一次撤销就等于删一条边了;如果上一次是删除操作的话,那么我们在上一次操作的时候就不要真的删除\(k\)条边。但是这样一来上一次操作又不好统计答案……其实也好弄,我们维护当前前\(i\)小的边形成的最小生成森林的边数和边权和就行了。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
#include <queue>
#include <stack>
const int maxn = 500005;
using pii = std::pair<int, int>;
int n, m;
int p[maxn], s[maxn];
void init_dsu() {
  for(int i = 1; i <= n; i ++) {
    p[i] = i; s[i] = 1;
  }
}
int get_fa(int x) {
  if(p[x] == x) {
    return x;
  } else {
    return get_fa(p[x]);
  }
}
pii merge_set(int x, int y) {
  x = get_fa(x); y = get_fa(y);
  if(x == y) return {-1, -1};
  if(s[x] > s[y]) std::swap(x, y);
  p[x] = y; s[y] += s[x];
  return {x, y};
}
void undo(const pii &e) {
  int x = e.first, y = e.second;
  if(x > 0) p[x] = x, s[y] -= s[x];
}

using event = std::pair<int, pii>;
struct Query {
  char typ; int x, y;
  Query(char c = '\0', int a = 0, int b = 0) {
    typ = c; x = a; y = b;
  }
};
const int maxm = 500005;
using ll = long long;
Query Q[maxm]; ll sit[maxm]; int siz[maxm];
ll ans[maxn];
void solve() {
  int sz = 0;
  init_dsu();
  std::stack<event> S;
  for(int i = 1; i <= m; i ++) {
    if(Q[i].typ == 'A') {
      sz ++; sit[sz] = sit[sz - 1]; siz[sz] = siz[sz - 1];
      int x = Q[i].x, y = Q[i].y;
      pii delta = merge_set(x, y);
      if(delta.first > 0) {
        sit[sz] += (ll)i; siz[sz] ++;
      }
      S.push({i, delta});
      ans[i] = (siz[sz] == n - 1) ? sit[sz] : 0;
    } else if(Q[i].typ == 'D') {
      int k = Q[i].x;
      if(Q[i + 1].typ == 'R') {
        int tt = sz - k;
        ans[i] = (siz[tt] == n - 1) ? sit[tt] : 0;
      } else {
        sz -= k;
        while(k --) {
          auto p = S.top().second; S.pop();
          undo(p);
        }
        ans[i] = (siz[sz] == n - 1) ? sit[sz] : 0;
      }
    } else {
      if(Q[i - 1].typ == 'A') {
        sz --;
        auto p = S.top().second; S.pop();
        undo(p);
      }
      ans[i] = (siz[sz] == n - 1) ? sit[sz] : 0;
    }
  }
  for(int i = 1; i <= m; i ++) {
    printf("%lld\n", ans[i]);
  }
}

int main() {
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= m; i ++) {
    char S[10]; scanf("%s", S);
    if(S[0] == 'A') {
      int x, y; scanf("%d%d", &x, &y);
      Q[i] = Query('A', x, y);
    } else if(S[0] == 'D') {
      int x; scanf("%d", &x);
      Q[i] = Query('D', x);
    } else {
      Q[i] = Query('R');
    }
  }
  solve();
  return 0;
}
AP 10th Telugu Quest 说:
Sep 14, 2022 10:09:13 PM

We advised contacting your Telugu teacher to get a chapter-wise practice model question paper for both levels of exams held under the school or board level and follow the link to download All AP SSC 10th Class Telugu Model Question Papers 2023 with Solutions. Every student everyone can download AP 10th Telugu Model Paper 2023 chapter-wise for paper-1, paper-2 exam theory, objective, AP 10th Telugu Question Paper multiple-choice questions (MCQ), Bit Question Bank with practice study material with IMP Question paper pdf with old scheme suggestions for AP 10th Class students 2023 to the Telugu Subject.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter