Codeforces Round 446 (Div. 1)

發表於 更新於 分類於 ， Disqus： 文章字數： 1.3k 所需閱讀時間 ≈ 4 分鐘
C(MST + Disjoint Set)

C大意

给一个有权无向图。进行q次询问，第i次询问ki个边，问所提到的ki个边能否同时出现在图的最小生成树上，返回YES或NO。

数据范围

图的边和点<=500'000

询问数q<=500'000,所有询问的边数的和sum(ki)<=500'000

时间空间(2s/256MB)

题解

不知道如果当时继续想下去，会不会想出解法，当时已经想到 并查集 和 边+未选取的边形成的环，已选取的 不能 大于max(未选取的)。感觉和正解的具体实现还差很远，但基础结论已经有了

标答说成那样，我也是没啥办法，我也想到了，没想到下一步。然后观摩了moejy0viiiiiv大佬的代码。 下面用举例来说明

首先，不要用官方的样例来想，想象图有且只有一个环，环上的边长是1,1,2,2,2

很直接可以知道只要不是选了所有的2，那么 都是可以同时存在于一个MST上的，那么选三个2的情况发生了什么，也就是上面说的选了三个2以后，在这个环上，未选取的最大只是1了。然后换一个角度看，如果我们已经先把图上所有的长度为1的链接好了，那么在新增加2的时候，就不应该形成环。

同样可以想象环上是1,1,2,2,2,3的情况，现在 尝试添加2的时候，就算全添加了，也不会直接形成环，和结论全选了2也能同时存在于一个MST是一样的。

其中要注意的是对于第一种情况，就算 询问中没有1 1，也不能选取 所有的2

因此把上述方法转化为伪代码

1
2
3
4
5
6
7
8
首先读入,所有边和询问，将询问 每个拆分，按长度第一序，询问号第二序 排序

从空开始，分别处理每一个询问中的1，将它们连接(并查集) 检验是否成环，如果成环该询问不可行

将所有的1相连接(并查集)不论在不在查询中，分别处理每一个询问中的2，将它们连接(并查集) 检验是否成环，如果成环该询问不可行
将所有的1 2相连接(并查集)不论在不在查询中，分别处理每一个询问中的3，将它们连接(并查集) 检验是否成环，如果成环该询问不可行
...
将所有的1 2...499'999相连接(并查集)不论在不在查询中，分别处理每一个询问中的500'000，将它们连接(并查集) 检验是否成环，如果成环该询问不可行

整理上面成循环就是

1
2
3
4
5
6
7
i=0
S(i) 表示连接完小于等于i的边的并查集
for(length=1~500'000):
  遍历每一查询
    选中一个包含该length的一个查询Q
    将Q中所有长length的边 和 S(length-1)相连 检查是否成环
  将所有长为length的边连入S(length-1)也就变成了S(length)

上面代码中 一个是既要利用已经连接的小于length的并查集，又要在每次 进行成环检测时 并查集能够复用，具体实现见下面moejy0viiiiiv大佬的代码，他用f来实现 可以逐渐增加利用的并查集，用p和mt来实现可复用 的每次检测。

代码

moejy0viiiiiv 的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
  using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head

const int N=501000;

int n,m,u[N],v[N],w[N],f[N],p[N],mt[N],T,wa[N];
int Q,k,id;
vector<int> eg[N];
vector<PII> qw[N];

int find(int x) {
  if (f[x]!=x) return f[x]=find(f[x]); else return x;
}
int find2(int x) {
  if (mt[x]!=T) mt[x]=T,p[x]=f[x];
  if (p[x]!=x) return p[x]=find2(p[x]); else return x;
}

int main() {
  scanf("%d%d",&n,&m);
  rep(i,0,m) {
    scanf("%d%d%d",u+i,v+i,w+i);
    eg[w[i]].pb(i);
  }
  rep(i,1,n+1) f[i]=i;
  scanf("%d",&Q);
  rep(i,0,Q) {
    scanf("%d",&k);
    rep(j,0,k) {
      scanf("%d",&id);
      --id;
      qw[w[id]].pb(mp(i,id));
    }
  }
  rep(i,1,500001) {
    sort(all(qw[i]));
    rep(j,0,SZ(qw[i])) {
      int x=u[qw[i][j].se],y=v[qw[i][j].se];
      find(x); find(y);
    }
    rep(j,0,SZ(qw[i])) {
      if (j==0||qw[i][j].fi!=qw[i][j-1].fi) T++;
      int x=u[qw[i][j].se],y=v[qw[i][j].se];
      if (find2(x)==find2(y))	wa[qw[i][j].fi]=1;
      p[find2(x)]=find2(y);
    }
    for (auto id:eg[i]) {
      int x=u[id],y=v[id];
      f[find(x)]=find(y);
    }
  }
  rep(i,0,Q) puts(wa[i]?"NO":"YES");
}

参考

题目

官方题解