为什么我用bitset维护原始编号的集合连原数据都过不了,维护缩点之后的编号集合就过了???
WA 90pts 代码如下:
#include <bitset>
#include <queue>
#include <ctime>
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define Reg register
#define ll long long
using namespace std;
const int maxn=2100,maxm=4000100;
int n,m,z,cnt,top,tot,head[maxn],bel[maxn];
int dfn[maxn],low[maxn],stk[maxn],vis[maxn];
int Xfrom[maxm],Yto[maxm],ru[maxn],ans;
bitset<maxn> S[maxn],tmp;
char Ed[maxn];
struct ED{
int to,nxt;
}e[maxm<<1];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<1)+(s<<3)+(ch^48);
ch=getchar();
}
return s*w;
}
inline void add(int u,int v){
e[++cnt].to=v;
e[cnt].nxt=head[u];
head[u]=cnt;
}
inline void tarjan(int u){
dfn[u]=low[u]=++tot,stk[++top]=u,vis[u]=1;
for(Reg int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}else if(vis[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u]){
int y=0;
z++;
do{
y=stk[top--];
vis[y]=0;
S[z][y]=1;
bel[y]=z;
}while(y!=u);
int p=S[z].count();
ans+=p*(p-1);
//这一步是统计内部贡献
}
}
queue<int> q;
int main(){
cin>>n;
for(Reg int i=1;i<=n;++i){
scanf("%s",Ed+1);
for(Reg int j=1;j<=n;++j){
if(Ed[j]=='1'){
add(i,j);
Xfrom[++m]=i;
Yto[m]=j;
}
}
}
for(Reg int i=1;i<=n;++i){
if(!dfn[i]) tarjan(i);
}
memset(head,0,sizeof(head));
cnt=0;
for(Reg int i=1;i<=m;++i){
if(bel[Xfrom[i]]==bel[Yto[i]])continue;
add(bel[Yto[i]],bel[Xfrom[i]]);
ru[bel[Xfrom[i]]]++;
}
for(Reg int i=1;i<=z;++i){
if(!ru[i]) q.push(i);
}
while(!q.empty()){
int u=q.front();
q.pop();
for(Reg int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
S[v]|=S[u];
ru[v]--;
if(!ru[v]) q.push(v);
}
}
for(Reg int i=1;i<=z;++i) ans+=S[i].count();
printf("%d\n",ans);
return 0;
}
/*
5
01100
00101
00011
00000
00000
*/