• 「拓扑排序」可达性统计


    可达性统计

    原题链接:可达性统计

    题目大意

    给你一张(n)个点(m)条边的有向无环图,分别统计从每个点出发能够到达的点的数量

    题目题解

    看到题意就知道要用到拓扑排序,但是拓扑排序的理论复杂度在30000的极限条件下会超时,这个时候我们考虑使用 (bitset),一个很好用的代替bool的防卡常技巧,详细的说明这里不说,可以去百度上查看相关运用

    //#define fre yes
    
    #include <queue>
    #include <bitset>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    const int N = 30005;
    int head[N << 1], to[N << 1], ver[N << 1];
    int in[N], ans[N];
    
    std::bitset<N> f[N];
    
    int tot, k;
    void addedge(int x, int y) {
        ver[tot] = y;
        to[tot] = head[x];
        head[x] = tot++;
    }
    
    int n, m;
    
    void toposort() {
        std::queue<int> q;
        for (int i = 1; i <= n; i++) {
            if(!in[i]) q.push(i);   
        }
        
        while(!q.empty()) {
            int t = q.front(); q.pop();
            ans[++k] = t;
            for (int i = head[t]; ~i; i = to[i]) {
                int v = ver[i];
                in[v]--;
                if(!in[v]) q.push(v);
            }
        }
    }
    
    int main() {
        memset(head, -1, sizeof(head));
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= m; i++) {
            int u, v;
            scanf("%d %d", &u, &v);
            addedge(u, v);
            in[v] ++;
        } toposort();
        // for (int i = 1; i <= n; i++) {
        //     printf("%d ", ans[i]);
        // }
        
        for (int  i = n; i >= 1; i--) {
            int j = ans[i];
            f[j][j] = 1;
            for (int x = head[j]; ~x; x = to[x]) {
                f[j] |= f[ver[x]];
            }
        }
        
        for (int i = 1; i <= n; i++) {
            printf("%d
    ", f[i].count());
        } return 0;
    }
    
  • 相关阅读:
    网络流与线性规划24题 之 餐巾计划问题
    待刷题目分类(一)
    bzoj1787 [Ahoi2008]Meet 紧急集合
    Hoj2634 How to earn more?
    poj3281 Dining
    浅谈数论(三)水仙花数
    poj1637 Sightseeing tour
    动态规划的思考(1)
    网络流-最大流问题 ISAP 算法解释(转自Renfei Song's Blog)
    poj1273 Drainage Ditches
  • 原文地址:https://www.cnblogs.com/Nicoppa/p/11549865.html
一二三 - 开发者的网上家园