4484: [Jsoi2015]最小表示（拓扑序+bitset维护连通性）

4484: [Jsoi2015]最小表示

题解:

bitset的题感觉都好巧妙啊QAQ。

因为题目中给出的是一个DAG，如果\(u->v\)这条边可以删去，等价于还存在一个更长的路径可以使得\(u\)到\(v\)。

这里的“更长”我们可以用拓扑序来搞，拓扑序大的相对于起点也肯定更长。那么思路就是对于每个点考虑删掉其出边，并且枚举边的时候拓扑序是从小到大的，然后来检验连通性。

但如果我们按照拓扑序来搞的话，很显然是错的。我们其实可以直接按着拓扑序反着来。这样的话后面点的连通性很容易知道，并且当前点与后面点的连通性也容易维护。

感觉拓扑序这种东西有点神奇，反着来经常能消除一些东西的影响，但具体什么我也不清楚QWQ。可能这样阶段划分清晰一点？反着来已处理过的与正在处理的关系是明确的，正着来正在处理的与后面的关系就不是很明确，就不是很容易维护信息。

如果有大佬知道可以给我明确一下。

代码如下：

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <iostream>

#include <cmath>

#include <bitset>

#include <queue>

using namespace std;

typedef long long ll;

const int N = 30005, M = 100005;

int n, m;

int in[N];

bitset <N> s[N] ;

struct Edge{

    int v, next ;

}e[M];

int head[N], tot;

void adde(int u, int v) {

    e[tot].v = v; e[tot].next = head[u]; head[u] = tot++;

}

int vist[N], t[N], a[N], b[N];

int T;

void Topsort() {

    queue <int> q;

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

    while(!q.empty()) {

        int u = q.front(); q.pop() ;

        vist[u] = ++T;

        t[T] = u;

        for(int i = head[u]; i != -1; i = e[i].next) {

            int v = e[i].v;

            if(--in[v] == 0) q.push(v) ;

        }

    }

}

bool cmp(int x, int y) {

    return vist[x] > vist[y] ;

}

int ans ;

void work(int u) {

    int tot = 0;

    s[u].set(u) ;

    for(int i = head[u]; i != -1; i = e[i].next) {

        int v = e[i].v;

        b[++tot] = v;

    }

    sort(b + 1, b + tot + 1, cmp) ;

    for(int i = tot; i >= 1; i--) {

        if(s[u][b[i]]) ans++;

        else s[u] |= s[b[i]] ;

    }

}

int main() {

    ios::sync_with_stdio(false); cin.tie(0) ;

    cin >> n >> m;

    memset(head, -1, sizeof(head)) ;

    for(int i = 1; i <= m; i++) {

        int u, v;

        cin >> u >> v;

        adde(u, v) ;++in[v] ;

    }

    Topsort() ;

    for(int i = 1; i <= n; i++) a[i] = i;

    sort(a + 1, a + n + 1, cmp) ;

    for(int i = 1; i <= n; i++) work(a[i]) ;

    cout << ans ;

    return 0;

}

巴特西

4484: [Jsoi2015]最小表示（拓扑序+bitset维护连通性）

4484: [Jsoi2015]最小表示

题解:

最新文章

热门文章