DDOSvoid's Blog

Luogu P6134 [JSOI2015]最小表示

发表于 分类于
本文字数： 1.2k 阅读时长 ≈ 1 分钟

题目描述

https://www.luogu.com.cn/problem/P6134

简要题意：给定 $n$ 个点 $m$ 条边的 $DAG$，求最多能删掉多少条边的同时不改变原图的连通性

$n\le 3\times 10^4,m\le 10^5$

Solution

容易发现删边的操作没有后效性，所以我们能删就删，如果边 $(u,v)$ 可以被删掉，那么则意味着一定存在 $x$ 使得 $u$ 可以到达 $x$ 且 $x$ 可以到 $v$，这个东西可以直接用 $bitset$ 维护

时间复杂度 $O(\frac{nm}{w})$

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
#include <iostream>
#include <bitset>
#include <queue>
#define maxn 30010
#define maxm 100010
using namespace std;

int n, m;

vector<int> G[maxn];

const int N = 30000;
bitset<N + 1> f[maxn], g[maxn];

int in[maxn], tp[maxn];
void topsort() {
    queue<int> Q; int cnt = 0; 
    for (int i = 1; i <= n; ++i)
        if (!in[i]) Q.push(i);
    while (!Q.empty()) {
        int u = Q.front(); Q.pop(); tp[++cnt] = u;
        for (auto v : G[u]) 
            if (--in[v] == 0) Q.push(v);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y;
        G[x].push_back(y); ++in[y];
    } topsort(); 
    for (int o = n, u = tp[o]; o; u = tp[--o]) 
        for (auto v : G[u]) f[u].set(v), f[u] |= f[u];
    for (int o = 1, u = tp[o]; o <= n; u = tp[++o]) 
        for (auto v : G[u]) g[v].set(u), g[v] |= g[u];
    int ans = 0; 
    for (int u = 1; u <= n; ++u)
        for (auto v : G[u]) ans += (f[u] & g[v]).count() > 0;
    cout << ans << "\n";
    return 0;
}