有些离谱
查看原帖
有些离谱
663976
Broken_Eclipse楼主2022/9/19 19:08

为什么我用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
*/
2022/9/19 19:08
加载中...