Logical Chain

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others) Total Submission(s): 71    Accepted Submission(s): 28 Problem Description Every time you come across a problem you've never seen before, haven't you thought of something that is familiar to you? If so, you might think of something else, then more and more things will come to your mind. This is what is called ''Logical Chain''. Lu Xun's work also described such interesting phenomenon. Assume there are  n  things, labeled by  1,2,...,n . Little Q's mind can be expressed by a  n×n  matrix  g . If he can think of  j  when he comes across  i , then  gi,j  is  1 , otherwise it's  0 . For two different things  u  and  v , if  u  can lead to  v  directly or indirectly and  v  can also lead to  u  directly or indirectly, then the pair  (u,v)  is called a ''Looping Pair''. Little Q's mind changes all the time. On  i -th day, there are  ki  positions  (u,v)  in matrix  g  flipped( 0  to  1  and  1  to  0 ). Please write a program to figure out the number of ''Looping Pairs'' after each day's all changes. Note :  (u,v)  and  (v,u)  should not be counted twice.   Input The first line of the input contains an integer  T(1≤T≤15) , denoting the number of test cases. In each test case, there are  2  integers  n,m(1≤n≤250,1≤m≤25000)  in the first line, denoting the number of things and days.\par For the next  n  lines, each line contains  n  integers  gi,1,gi,2,...,gi,n(0≤gi,j≤1,gi,i=0) , denoting the matrix  g . For the next  m  parts, there is an integer  ki(1≤ki≤10)  in the first line, denoting the number of changes happened on that day. For the next  ki  lines, each line contains  2  integers  u,v(1≤u,v≤n,u≠v) , denoting a changed position in  g . It is guaranteed that each position will be changed at most once per day.   Output For each day, print a single line containing an integer, denoting the number of ''Looping Pairs'' after that day's all changes.   Sample Input 1 4 2 0010 1000 0000 0000 3 1 4 3 2 1 2 2 4 3 2 3   Sample Output 3 6   Source 2017 Multi-University Training Contest - Team 4    Recommend liuyiding

题目大意：

    给你一张n个结点(1<=n<=250)的有向图，m(1<=m<=25000)组操作，每次翻转一些边，求每组操作后可以相互到达的点的对数。

解题思路：

    很容易就可以发现，每个点数为t的强连通分量对答案的贡献为t(t-1)/2。那么我们只要每次找到各个强连通分量即可。由于这里存在边的翻转操作，所以我们只能使用邻接矩阵来表示图。对于邻接矩阵表示的图Kosaraju算法的时间复杂度为O(n^2)，那么总复杂度为O(m*n*n)，这样会T。面对稠密图，Kosaraju算法的瓶颈在于寻找与点$x$相连且未访问过的点。gx​​由于超出时间限制不是很多，我们就可以用bitset优化，使时间复杂度降到O(m*n*n/64)就可以通过了。

    下面代码使用了gcc的__builtin_函数，这里就简单介绍__builtin_函数中处理二进制位的函数：

int __builtin_ffs (unsigned x) 返回x中最后一个1是从右往左第几位

int __builtin_popcount (unsigned x) 返回x中1的个数

int __builtin_ctz (unsigned x) 返回x末尾0的个数(x等于0时未定义)

int __builtin_clz (unsigned x) 返回x中前导0的个数(x等于0时未定义)

int __builtin_parity (unsigned x) 返回x中1的奇偶性

AC代码：

#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <ctime> #include <vector> #include <queue> #include <stack> #include <deque> #include <string> #include <map> #include <set> #include <list> using namespace std; #define INF 0x3f3f3f3f3f3f3f3f #define LL long long #define fi first #define se second #define mem(a,b) memset((a),(b),sizeof(a)) const int MAXV=250+3; struct Bitset//用unsigned数组实现bitset，为了使用__builtin_ctz() { unsigned v[8];//8个unsigned表示8*32=256位 void reset()//清零 { for(int i=0;i<8;++i) v[i]=0; } void set(int x)//把某一位设为1 { v[x>>5]|=1u<<(x&31); } void flip(int x)//翻转某一位 { v[x>>5]^=1u<<(x&31); } bool test(int x)//返回某一位是否为1 { return v[x>>5]>>(x&31)&1; } }vis, G[MAXV], rG[MAXV];//访问标记，原图，反向图 int V, M; int ord[MAXV];//dfs序 int num;//当前强连通分量的结点数 inline void flipedge(int x, int y)//翻转一条边 { G[x].flip(y); rG[y].flip(x); } void dfs0(int x)//正向dfs { vis.flip(x); for(int i=0;i<8;++i) while(true) { unsigned tmp=vis.v[i]&G[x].v[i];//得到相连的没有访问过的点的状压 if(!tmp) break; dfs0(i<<5|__builtin_ctz(tmp));//下一个相连的没有访问过的点 } ord[++ord[0]]=x; } void dfs1(int x)//反向dfs { vis.flip(x); ++num; for(int i=0;i<8;++i) while(true) { unsigned tmp=vis.v[i]&rG[x].v[i]; if(!tmp) break; dfs1(i<<5|__builtin_ctz(tmp)); } } int kosaraju()//每次查询的答案 { vis.reset(); int res=0; ord[0]=0; for(int i=0;i<V;++i) vis.set(i); for(int i=0; i<V;++i) if(vis.test(i)) dfs0(i); for(int i=0;i<V;++i) vis.set(i); for(int i=V;i;--i) if(vis.test(ord[i]))//找到一个新的强连通分量 { num=0; dfs1(ord[i]); res+=num*(num-1)/2; } return res; } int main() { int T_T; scanf("%d",& T_T); while(T_T--) { scanf("%d%d",&V, &M); for(int i=0;i<V;++i) { G[i].reset(); rG[i].reset(); } for(int i=0;i<V;++i) { char s[MAXV]; scanf("%s", s); for(int j=0;j<V;++j) if(s[j]=='1') flipedge(i, j); } while(M--) { int n; scanf("%d", &n); while(n--) { int a, b; scanf("%d%d", &a, &b); flipedge(a-1, b-1); } printf("%d\n", kosaraju()); } } return 0; }