HDU6072 Logical Chain

题意：动态修改图 \(G\) 的边集，求每次修改后的 \(\sum c\times (c−1) / 2\) （记每个强连通分量中的点数量为 \(c\) ）。其中修改操作共 \(m\) 次，每次最多改 \(k\) 条边。\(1≤m≤25000,1≤k≤10\)，图 \(G\) 中点数为 \(n\) ，\(1≤n≤250\)。

题解：\(tarjan\)由于要遍历所有边，复杂度 \(\mathcal{O}((V+E)\times m)\)，在稠密图中效率较低；而使用邻接矩阵存储边集状态，利用 \(Kosaraju\) 解决的复杂度将达到 \(\mathcal{O}(V^2\times m)\) ，然后可以利用 bitset 优化边集的存储，加速后继点的查找，复杂度 \(\mathcal{O}(\frac{V^2\times M}{32})\)

#include<iostream>

#include<cstdio>

#include<cstring>

#include<vector>

#define R register int

using namespace std;

namespace Luitaryi {

inline int g() { R x=0,f=1;

  register char s; while(!isdigit(s=getchar())) f=s=='-'?-1:f;

  do x=x*10+(s^48); while(isdigit(s=getchar())); return x*f;

} const int B=8,D=5,L=31,N=260;

struct bitset {

  unsigned dat[B];

  inline void reset() {memset(dat,0,B<<2);}

  inline void set() {memset(dat,0xff,B<<2);}

  inline void set(int x) {dat[x>>D]|=1u<<(x&L);}

  inline void flip(int x) {dat[x>>D]^=1u<<(x&L);}

  inline bool test(int x) {return dat[x>>D]>>(x&L)&1;}

}vis,e[N],re[N];

vector<int> s;

int n,m,num,T;

#define u32 unsigned

inline void dfs1(int u) {

  vis.flip(u);

  for(R i=0;i<B;++i) {

    while(20040109) {

      register u32 tmp=vis.dat[i]&e[u].dat[i];

      if(!tmp) break;

      dfs1(i<<D|__builtin_ctz(tmp));

    }

  } s.push_back(u);

}

inline void dfs2(int u) {

  vis.flip(u),++num;

  for(R i=0;i<B;++i) {

    while(20021204) {

      register u32 tmp=vis.dat[i]&re[u].dat[i];

      if(!tmp) break;

      dfs2(i<<D|__builtin_ctz(tmp));

    }

  }

}

inline void Kosaraju() {

  s.clear(),vis.set(); R ans=0;

  for(R i=0;i<n;++i) if(vis.test(i)) dfs1(i);

  vis.set(); for(R i=n-1;~i;--i) {

    if(vis.test(s[i])) {

      num=0;

      dfs2(s[i]);

      ans+=num*(num-1)/2;

    }

  } printf("%d\n",ans);

}

inline void main() {

  T=g(); while(T--) {

    n=g(),m=g();

    for(R i=0;i<n;++i) e[i].reset(),re[i].reset();

    for(R i=0;i<n;++i) { register char s[N];

      scanf("%s",s);

      for(R j=0;j<n;++j) if(s[j]=='1')

        e[i].flip(j),re[j].flip(i);

    }

    while(m--) { R t=g();

      while(t--) { R u,v;

        u=g(),v=g();

        e[u-1].flip(v-1),re[v-1].flip(u-1);

      } Kosaraju();

    }

  }

}

} signed main() {Luitaryi::main(); return 0;}

2019.12.18

巴特西

HDU6072 Logical Chain

最新文章

热门文章