icontofig | 发布于 2019-10-12 13:42:57 | 阅读量 120 | bitset topsort
发布于 2019-10-12 13:42:57 | bitset topsort


题目大意

给定一个n个点的DAG(有向无环图),每个点一开始都是白色,每一次操作会改变一个指定的点的颜色,并询问当前有多少对白点对(u,v)互相可达(存在一条从u到v的有向路径使得路径上全部为白色的点)。

题解

可以认为黑色点与其他点都不连通。

所以我们每一次更改点的颜色实际都是再更改图的联通关系。

我们可以通过搜索、topsort、floyd-warshell算法等计算两点间的联通关系(这时候就通过位运算或|来代替Floyd原先的+就好了,因为位运算或即为逻辑加操作)。

但是我们发现这样复杂度是不对的……

这三种最快的topsort复杂度也是O(qnm)的,明显不符合我们的复杂度要求。

这时候我们注意到对于联通关系,两点间的联通关系也即用0表示不连通,1表示联通。

我们对于更新也是这样的:

假设当前检索点为u,下一个点为v,则对于所有联通u的点k,假设mp[i][j]表示是否可从i联通到j,则有

mp[k][v] = mp[k][u]; ----> mp[k][v] |= mp[k][u];

可以看到这个更新过程实际上只有位运算的或操作,只有0和1的运算,所以可以用bitset进行加速。

当我们检索到当前的点u时,先预处理设定mp[u][u] = 1,表示当前点可以到达当前点。最终因为答案是算不相同的点u和v联通个数,所以最后进行统计的时候答案整体-n即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 305;
int d[maxn],tmp[maxn];
bitset<305>con[maxn];
queue<int>qk;
vector<int>g[maxn];
int n,m,q;
int a,b;
int c[maxn],vis[maxn];
void topsort(){
    for(int i = 1;i <= n;++i)
        con[i].reset();
    for(int i = 1;i <= n;++i){
        if(!c[i])
            con[i][i] = 1;
        vis[i] = 0;
    }
    for(int i = 1;i <= n;++i){
        tmp[i] = d[i];
        if(!d[i]){
            qk.push(i);
            vis[i] = 1;
        }
    }
    while(!qk.empty()){
        int now = qk.front();
        qk.pop();
        for(int i = 0;i < g[now].size();++i){
            int v = g[now][i];
            if(c[v] == 0 && c[now] == 0)
                con[v] |= con[now];
            tmp[v] -= 1;
            if(!tmp[v]){
                vis[v] = 1;
                qk.push(v);
            }
        }
    }
    int ans = 0;
    for(int i = 1;i <= n;++i){
        if(!c[i])
            ans += con[i].count() - 1;
    }
    printf("%d\n",ans);
    return;
}
int main(){
    while(scanf("%d%d%d",&n,&m,&q) != EOF){
        for(int i = 1;i <= n;++i){
            c[i] = 0;
            d[i] = 0;
            g[i].clear();
        }
        for(int i = 1;i <= m;++i){
            scanf("%d%d",&a,&b);
            d[b]++;
            g[a].push_back(b);
        }
        while(q--){
            scanf("%d",&a);
            c[a] ^= 1;
            topsort();
        }
    }
    return 0;
}



内容更新于: 2019-10-12 13:42:59
链接地址: http://blog.leanote.com/post/icontofig/6e2a36d27dfc

上一篇: HAOI2018 染色 NTT 组合数

下一篇: 牛客欢乐赛4 2017湘潭市赛 C.Intersection 线性基 + 秩(线性代数题目)

120 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航