颜色限制(restriction)

时间限制: 1000ms
空间限制: 524288kB
输入文件名: restriction.in
输出文件名: restriction.out

题目描述

有一个 n 点 m 边的无向图,有 k 种颜色编号为 0∼k−1,每条边有一种颜色。对于每种颜色,请判断假如删去所有这种颜色的边,得到的图是否连通?是否是一棵树?

输入格式

从文件 restriction.in 中读入。
第一行三个整数 n,m,k ,表示点数、边数、颜色数。接下来 m 行,每行三个整数 u,v,c ,表示一条无向边(u,v) 的颜色为 c

输出格式

输出到文件 restriction.out 中。
一行两个整数 p,q ,表示满足删去后图连通的颜色数和删去后图是树的颜色数。

样例

Input 1
5 5 4
1 2 0
2 3 0
3 4 1
4 5 2
5 2 3
Output 1
3 3
Input 2
5 5 2
1 2 0
2 3 0
3 4 0
4 5 0
5 2 0
Output 2
1 0

数据范围

对于全部数据:1\le n,m\le 10^52\le k\le 10^51\le u \neq v\le n0\le c
图无自环,但可能有重边。

子任务 $n\le$ $m\le$ $k\le$ 所有颜色相等 分值
$1$ $300$ $300$ $300$ $10$
$2$ $10^3$ $10^5$ $10^3$ $30$
$3$ $10^5$ $10^5$ $2$ $10$
$4$ $10^5$ $10^5$ $10^5$ $10$
$5$ $10^5$ $10^5$ $10^5$ $40$

样例解释

样例 1 解释

除了颜色 0 以外,其他颜色删去后均得到树,而删去0 图不连通。


题目分析

题面还是比较简单的,就是有各种颜色的边,问去掉一个边,图是否连通,是否为树。

先来看第二个小问。

问一个图 G\lang E, V \rang 是否为树,我们只要判断 \lbrack V = E – 1\rbrack 即可,做一个统计,复杂度 \mathcal{O}(m + k)

再看第一小问。

数据范围很大,每次遍历减去某个颜色的边绝对不行。我们先将颜色编号指向该颜色的边。
一开始想到,映射完毕之后可以将这些颜色加入到并查集,然后每次枚举去掉一个点之后的并查集,看是否连通。但是这样时间复杂度还是很高,为\mathcal{O}(k(m + n))

所以我们就要介绍一种并查集的写法:

并查集启发式合并

启发式合并放弃了路径压缩,但是它尽可能地将这棵树压缩到最小。
很明显,我们根据树的大小或者深度合并,是最经济的做法。对于大部分可持久化算法,根据树的大小合并会节省一些空间。

具体做法:

开一个 cnt 数组,记录并查集的大小,初始化为1。在每次合并的时候,都将 cnt 小的一方合并到 cnt 大的一方。

并查集撤销
  • 对于启发式并查集,如果我们知道合并顺序,其实可以开一个栈,正序合并,逆序拆解,具体可以看本题代码。
  • 对于单点撤销,考虑别的做法。
    • 初始化的时候,维护一个数据范围之外的 cnt,在删除的时候,将删除的点的父亲挂载为 cnt ,并将 cnt 的父亲挂为 cnt 自己,cnt++
扩展:树上启发式合并

做法讲解:

  • 遍历每一个节点

  • 递归解决所有的轻儿子,同时消除递归产生的影响

  • 递归重儿子,不消除递归的影响

  • 统计所有轻儿子对答案的影响

  • 更新该节点的答案

  • 删除所有轻儿子对答案的影响

例题(更新)

[例题] CF600E


我们继续看本题。思路其实跟树上问题类似,都是要利用重链部分对解进行计算。
考虑分治。设 solve(l,r) 表示解决删去的颜色在 [l,r] 时的问题。先将颜色在 [l,mid] 的边加到图中,递归 solve(mid+1,r) 即可求得删去的颜色在 [mid+1,r] 的所有答案;同理可以求得删去的颜色在 [l,mid] 的所有答案。使用可撤销并查集维护连通性即可。

AC Code

time: 806ms, memory: 9552kb, score: 100, status: Accepted
本题卡快读

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxd(x, y) ((x) > (y) ? (x) : (y))
#define mind(x, y) ((x) < (y) ? (x) : (y))
#define abs_sub(x, y) ((x) > (y) ? (x) - (y) : (y) - (x))
const double eps = 1e-8;
const double pi = acos(-1.0);
const int MAXN = 1e5 + 100;
struct edge{int from, to;};
int fa[MAXN];
int cnt[MAXN];
int n, m, k;
vector<edge> G[100010];
inline void init() {
  for(int i = 1; i <= n; i++) {
    fa[i] = i, cnt[i] = 1;
  }
}
inline int read() {
  char ch = getchar(); int x = 0, f = 1;
  for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
  for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
  return x;
}
int find(int pos) {
  return fa[pos] == pos ? pos : find(fa[pos]);
}
int ans1 = 0, ans2 = 0;
void dfs(int l, int r) {//访问到这里,应该是提前被删除或者没有加的
  if(l == r) {
    if(cnt[find(1)] == n) {
      ans1++;
      if(m - (int)G[l].size() == n - 1) ans2++;
    }
    return;
  }
  int mid = (l + r) >> 1;
  stack<pair<int, int>> st;
  for(int i = l; i <= mid; i++) {
    for(auto j : G[i]) {
      int u = find(j.from), v = find(j.to);
      if(u != v) {
        if(cnt[u] < cnt[v]) swap(u, v);
        st.emplace(u, v);
        fa[v] = u, cnt[u] += cnt[v];
      }
    }
  }
  dfs(mid + 1, r);
  while(!st.empty()) {
    auto t = st.top(); st.pop();
    fa[t.second] = t.second;
    cnt[t.first] -= cnt[t.second];
  }
  for(int i = mid + 1; i <= r; i++) {
    for(auto j : G[i]) {
      int u = find(j.from), v = find(j.to);
      if(u != v) {
        if(cnt[u] < cnt[v]) swap(u, v);
        st.emplace(u, v);
        fa[v] = u, cnt[u] += cnt[v];
      }
    }
  }
  dfs(l, mid);
  while(!st.empty()) {
    auto t = st.top(); st.pop();
    fa[t.second] = t.second;
    cnt[t.first] -= cnt[t.second];
  }
}
int main()
{
  freopen("restriction.in", "r", stdin);
  // freopen("restriction.out", "w", stdout);
 
  n = read(), m = read(), k = read();
  init();
  int u, v, c;
  for(int i = 1; i <= m; i++) {
    u = read(), v = read(), c = read();
    edge E;
    E.from = u, E.to = v;
    G[c].emplace_back(E);
  }
  dfs(0, k - 1);
  printf("%d %d\n", ans1, ans2);
  return 0;
}