CH 2101 可达性统计

题目链接

题目描述

给定一张N个点M条边的有向无环图,分别统计从每个点出发能够到达的点的数量。

输入格式

第一行两个整数N,M,接下来M行每行两个整数x,y,表示从x到y的一条有向边。

输出格式

输出共N行,表示每个点能够到达的点的数量。

数据范围

1≤N,M≤30000

输入样例:

1
2
3
4
5
6
7
8
9
10
11
10 10
3 8
2 3
2 5
5 9
5 9
2 3
3 9
4 8
2 10
4 9

输出样例:

1
2
3
4
5
6
7
8
9
10
1
6
3
3
2
1
1
1
1
1

题意分析:

题目已经说明白,给我们的是DAG(有向无环图)。既然是DAG,可以很容易的联想到拓扑排序。题目让我们统计每个点出发能到达的点的数量,我们可以先模拟一下样例,如下图(只例举出1,2,3三个点)。

红色是2能到达的点、绿色是3能到达的点

题解:

综上所述,设从点 x 出发能够到达的点构成的集合是 f(x),从点 x 出发能够到达的点,是从 x 的各个后继节点 y 出发能够到达的点的并集,再加上点 x 自身 。

f(2) = f(3) ∪ f(5) ∪ f(10) = …

先按照拓扑排序算法求出拓扑序,然后按照拓扑序的倒叙进行计算——因为在拓扑序中,任意一条边 (x , y),x 都排在 y 之前。

关于状态压缩 bitset容器:

1
转载:https://oi-wiki.org/ds/stl/bitset/
介绍

std :: bitset 是标准库中的一个固定大小序列,其储存的数据只包含 0/1

众所周知,由于内存地址是按字节即 byte 寻址,而非比特 bit ,

我们一个 bool 类型的变量,虽然只能表示 0/1 , 但是也占了 1byte 的内存

bitset 就是通过固定的优化,使得一个字节的八个比特能分别储存 8 位的 0/1

对于一个 4 字节的 int 变量,在只存 0/1 的意义下, bitset 占用空间只是其

在某些情况下通过 bitset 可以使你的复杂度除以 32

当然, vector 的一个特化 vector<bool> 的储存方式同 bitset 一样,区别在于其支持动态开空间,

bitset 则和我们一般的静态数组一样,是在编译时就开好了的。

那么为什么要用 bitset 而非 vector<bool> ?

通过以下的介绍,你可以更加详细的看到 bitset 具备的方便操作

1
#include <bitset>  // 包含 bitset 的头文件
运算符
  • operator[] : 访问其特定的一位

  • operator ==/!= : 比较两个 bitset 内容是否完全一样

  • operator &=/|=/^=/~ : 进行按位与/或/异或/取反操作

  • operator <</>>/<<=/>>= : 进行二进制左移/右移

  • operator <</>> : 流运算符,这意味着你可以通过 cin/cout 进行输入输出

    vector<bool> 只具有前两项

成员函数
  • test() : 它和 vector 中的 at() 的作用是一样的,和 [] 运算符的区别就是越界检查
  • count() : 返回 true 的数量
  • set() : 将整个 bitset 设置成 true , 你也可以传入参数使其设置成你的参数
  • reset() : 将整个 bitset 设置成 false
  • flip() : 翻转该位 (0 变 1,1 变 0), 相当于逻辑非/异或 1
  • to_string() : 返回转换成的字符串表达
  • to_ulong() : 返回转换成的 unsigned long 表达 ( long 在 NT 及 32 位 POSIX 系统下与 int 一样,在 64 位 POSIX 下与 long long 一样)
  • to_ullong() C++11, 返回转换成的 unsigned long long 表达

这些 vector<bool> 基本都没有

作用

一般来讲,我们可以用 bitset 优化一些可行性 DP, 或者线筛素数 ( notprime 这种 bool 数组可以用 bitset 开到 之类的)

它最主要的作用还是压掉了内存带来的时间优化, 的常数优化已经可以是复杂度级别的优化了,比如一个 的 算法, 显然很卡,在常数大一点的情况下必然卡不过去,O(松)不能算!, 这时候如果我们某一维除以 32, 则可以比较保险的过了这道题

其实 bitset 不光是一个容器,更是一种思想,我们可以通过手写的方式,来把 long long 什么的压成每 bit 表示一个信息,用 STL 的原因更多是因为它的运算符方便

AC代码:

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
#include<bits/stdc++.h>
using namespace std;

const int maxn = 30000 + 5;
int n,m;
int in[maxn];
vector<int> e[maxn];
vector<int> topo;
bitset<maxn> f[maxn];

inline void toposort()
{
topo.clear();
queue<int> q;

for(int i = 1;i <= n;++i)
if(in[i] == 0) q.push(i);

while(q.size())
{
int u = q.front();
q.pop();

topo.push_back(u);

for(int i = 0;i < e[u].size();++i)
if(--in[e[u][i]] == 0) q.push(e[u][i]);
}

}

void init()
{
cin >> n >> m;
memset(in,0,sizeof(in));

for(int i = 1;i <= m;++i)
{
int x,y;
cin >> x >> y;
in[y]++;
e[x].push_back(y);
}
}

void find()
{
toposort();

for(int i = topo.size() - 1;i >= 0;i--)
{
int x = topo[i];
f[x].reset(),f[x][x] = 1;
for(int k = 0;k < e[x].size();++k)
f[x] |= f[e[x][k]];
}

for(int i = 1;i <= n;++i)
cout << f[i].count() << endl;
}

int main(int argc, char const *argv[])
{
ios::sync_with_stdio(false);

init();

find();

return 0;
}
本站文章除注明转载外均为原创,未经允许不要转载哇. ヾ(゚ー゚ヾ) http://chicago01.top/2019/01/30/做题记录-CH-2101-可达性统计/index.html
Compartir