[JSOI2010]连通数

曾经终败给现在 2021-10-01 01:18 235阅读 0赞

这个题目有毒。

我同学跟我说这个是强连通分量水题，然后我就打$tarjan$，结果$WA ，WA，WA$

思考许久没想出来哪里错了。

于是仔细思考，可以用BFS做，于是我很愉快的打了一个$BFS$，AC啦！

原来 一道 省选/NOI- 的JS省选紫题就这么水过了

愉快的打了个 普及/提高-

回家仔细思考哪里错了。

发现自己有不少写错了

1）建边的时候 把 $S\[j\]==‘1’$写成了$‘0’$

2）强连通分量 没用 ins 还有 还有 把 $tarjan(to)$ 写成了 $tarjan(i)$

3）new\_E 把 所有的 $e\[i\]$ 写成了 $G\[i\]$ （看来够昏头的，机房效率不高啊）

4）solve 里 把所有的$G\[x\]$写成了 $e\[x\] $（正好写反了！！！）

5）没开long long

这是我的AC旅程

![1460047-20180913192316882-1579012201.png][]

好了，不说自己的经历了，讲正解怎么做的

首先，BFS真的很好想，对，就是直接对于每个点遍历其路径即可，然后+n即可（i和i肯定是连通的么）。

// Author : harry
    // Language : C++ (GNU C++ 11)
    // Upload : luogu
    // Time : 2018.9.13 
    // Problem : 连通数 【bfs版】 
    // Tell Myself : Think Twice Code Once
    // All rights reserved
    
    #include <map>
    #include <set>
    #include <cmath>
    #include <ctime>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <cstdio>
    #include <cctype>
    #include <string>
    #include <cstring>
    #include <cassert>
    #include <climits>
    #include <cstdlib>
    #include <iostream>
    #include <algorithm>
    #include <functional>
    using namespace std ;
    
    #define rep(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
    #define Rep(i,a,b) for (int (i)=(a)-1;(i)<(b);(i)++)
    #define REP(i,a,b) for (int (i)=(a);(i)>=(b);(i)--)
    #define reg(i,x) for (int (i)=head[x];(i);i=e[i].next)
    #define clear(a) memset(a,0,sizeof(a))
    
    #define ull unsigned long long
    #define ll long long
    #define ls ((x)<<1)
    #define rs ((x)<<1|1)
    #define mp make_pair
    #define pb push_back
    #define fi first
    #define se second
    #define endl '\n'
    #define Pii pair<int,int>
    
    const int N = 2010 ;
    const int iinf = INT_MAX/2 ;
    const ll linf = LONG_MAX/2 ;
    const int MOD = 1e9+7 ;
    
    inline int read(){
        int X=0,w=0; char ch=0;
        while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
        while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
        return w?-X:X;
    }
    
    void write(int x){
         if(x<0) putchar('-'),x=-x;
         if(x>9) write(x/10);
         putchar(x%10+'0');
    }
    
    int vis[N] ;
    vector<int> e[N] ;
    ll ans=0;
    int n ;
    
    void bfs(int rt){
        queue <int> q ;
        memset(vis,0,sizeof(vis)) ;
        q.push(rt) ;
        vis[rt]=1 ;
        while(!q.empty()){
            int x=q.front();q.pop() ;
            for (int i=0;i<e[x].size();i++)
            if (!vis[e[x][i]]){
                ans++ ;
                vis[e[x][i]]=1 ;
                q.push(e[x][i]) ;
            }
        }
    }
    
    string S ;
    
    int main(){
        scanf("%d",&n) ;
        for (int i=1;i<=n;i++){
            cin>>S ;
            for (int j=0;j<n;j++) if (S[j]=='1') e[i].pb(j+1) ;
        }
        
        for (int i=1;i<=n;i++) bfs(i) ;
        printf("%lld\n",ans+n) ;
    }

强连通的做法就要稍微难想一点。

嗯，首先这个题目给了我们一个定义：连通数：指途中可达点对的个数。

其实首先这个定义我就并没有十分看懂，

其实这个东西的意思非常简单，就是针对每一个点，

我们计算这个点所能够到达的点的数量之和，

（算上自身）然后将所有点的这个数量加起来就是连通数了。

可以通过缩点优化

缩完点之后，我们重新构图。

记录$sum\[i\]$ 表示i（缩完点后的新点）所表示的点包含旧图中点的个数

时间复杂度 $O(n^3)$

$f\[i\]$ 表示 $i$ 能到达的点集 $s$ （用bitset优化）

构完图之后，把入度为0的点加入队列。

之后像类似拓扑排序那样当入度为0就加入队列

然后对于每一次 即将更新的 用这个更新 $f\[G\[x\]\[i\]\]|=f\[x\]$

然后统计一下答案就AC了

回顾之后感觉还是挺水的

// Author : harry
    // Language : C++ (GNU C++ 11)
    // Upload : luogu 
    // Time : 2018.9.13
    // Problem : 连通数 【强连通版】 
    // Tell Myself : Think Twice Code Once
    // All rights reserved
    
    #include <map>
    #include <set>
    #include <cmath>
    #include <ctime>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <bitset>
    #include <cstdio>
    #include <cctype>
    #include <string>
    #include <cstring>
    #include <cassert>
    #include <climits>
    #include <cstdlib>
    #include <iostream>
    #include <algorithm>
    #include <functional>
    using namespace std ;
    
    #define rep(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
    #define Rep(i,a,b) for (int (i)=(a)-1;(i)<(b);(i)++)
    #define REP(i,a,b) for (int (i)=(a);(i)>=(b);(i)--)
    #define reg(i,x) for (int (i)=head[x];(i);i=e[i].next)
    #define clear(a) memset(a,0,sizeof(a))
    
    #define ull unsigned long long
    #define ll long long
    #define ls ((x)<<1)
    #define rs ((x)<<1|1)
    #define mp make_pair
    #define pb push_back
    #define fi first
    #define se second
    #define endl '\n'
    #define Pii pair<int,int>
    
    const int N = 2010 ;
    const int iinf = INT_MAX/2 ;
    const ll linf = LONG_MAX/2 ;
    const int MOD = 1e9+7 ;
    
    inline int read(){
        int X=0,w=0; char ch=0;
        while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
        while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
        return w?-X:X;
    }
    
    void write(int x){
         if(x<0) putchar('-'),x=-x;
         if(x>9) write(x/10);
         putchar(x%10+'0');
    }
    
    vector<int> e[N],G[N] ;
    
    int low[N],dfn[N],ins[N],col[N],a[N],ind[N] ;
    stack <int> s ;
    
    bitset <N> f[N] ;
    int n,sum,t;
    ll ans ;
    
    void tarjan(int rt){
        dfn[rt]=low[rt]=++t ;
        ins[rt]=1;s.push(rt) ;
        
        for (int i=0;i<e[rt].size();i++){
            int to=e[rt][i] ;
            if (!dfn[to]){
                tarjan(to) ;
                low[rt]=min(low[rt],low[to]) ;
            }
            else if (ins[to]) low[rt]=min(low[rt],dfn[to]) ;
        }
        
        if (dfn[rt]==low[rt]){ //缩点 
            col[rt]=++sum ;
            ins[rt]=-1 ;
            a[sum]=1 ;
            while(s.top()!=rt){
                col[s.top()]=sum ;
                ins[s.top()]=-1 ;
                a[sum]++ ;
                s.pop() ;
            }
            s.pop() ;
        }
    }
    
    void new_E() { //重新构图 
        for (int i=1;i<=n;i++)
        for (int j=0;j<e[i].size();j++)
        if (col[i]!=col[e[i][j]]){
            G[col[i]].pb(col[e[i][j]]) ;
            ind[col[e[i][j]]]++ ;
        }
    }
    
    void solve(){
    	queue <int> q ;
    	while (!q.empty()) q.pop() ;
        for (int i=1;i<=sum;i++) f[i][i]=1 ;
    	for (int i=1;i<=sum;i++) if (!ind[i]) q.push(i) ; 
        while(!q.empty()){
            int x=q.front();q.pop() ;
            for (int i=0;i<G[x].size();i++){
                f[G[x][i]]|=f[x] ;
                ind[G[x][i]]-- ;
                if (!ind[G[x][i]]) q.push(G[x][i]) ;
            }
        }
    }
    
    string S ;
    
    int main(){
        scanf("%d",&n) ;
        for (int i=1;i<=n;i++){
            cin>>S ;
            for (int j=0;j<n;j++) if (S[j]=='1') e[i].pb(j+1) ;
        }
        
        for (int i=1;i<=n;i++) if (!ins[i]) tarjan(i) ;
        
        new_E() ;
        solve() ;
        
        for (int i=1;i<=sum;i++)
        for (int j=1;j<=sum;j++)
        if (f[i][j]) ans+=a[i]*a[j] ;
        printf("%lld\n",ans) ;
    }

受f\[i\]的启发，感觉floyd也能做这题

也是bitset

如果 $f\[j\]\[i\]$  $f\[j\]|=f\[i\]$

然后统计一下也可以AC

// Author : harry
    // Language : C++ (GNU C++ 11)
    // Upload : luogu 
    // Time : 2018.9.13
    // Problem : [JSOI2010]连通数 【floyd 版】 
    // Tell Myself : Think Twice Code Once
    // All rights reserved
    
    #include <map>
    #include <set>
    #include <cmath>
    #include <ctime>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <bitset>
    #include <cstdio>
    #include <cctype>
    #include <string>
    #include <cstring>
    #include <cassert>
    #include <climits>
    #include <cstdlib>
    #include <iostream>
    #include <algorithm>
    #include <functional>
    using namespace std ;
    
    #define rep(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
    #define Rep(i,a,b) for (int (i)=(a)-1;(i)<(b);(i)++)
    #define REP(i,a,b) for (int (i)=(a);(i)>=(b);(i)--)
    #define reg(i,x) for (int (i)=head[x];(i);i=e[i].next)
    #define clear(a) memset(a,0,sizeof(a))
    
    #define ull unsigned long long
    #define ll long long
    #define ls ((x)<<1)
    #define rs ((x)<<1|1)
    #define mp make_pair
    #define pb push_back
    #define fi first
    #define se second
    #define endl '\n'
    #define Pii pair<int,int>
    
    const int N = 2010 ;
    const int iinf = INT_MAX/2 ;
    const ll linf = LONG_MAX/2 ;
    const int MOD = 1e9+7 ;
    
    inline int read(){
        int X=0,w=0; char ch=0;
        while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
        while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
        return w?-X:X;
    }
    
    void write(int x){
         if(x<0) putchar('-'),x=-x;
         if(x>9) write(x/10);
         putchar(x%10+'0');
    }
    
    string s ;
    bitset <N> f[N];
    int n ;
    ll ans ;
    
    int main(){
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            cin>>s ;
            for (int j=0;j<n;j++) if(s[j]=='1') f[i][j+1]=1;
            f[i][i]=1;
        }
        
        for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
        if (f[j][i]) f[j]|=f[i];
        
        for(int i=1;i<=n;i++) ans+=f[i].count(); 
        printf("%lld",ans);
    }

感谢阅读！

转载于:https://www.cnblogs.com/harryhqg/articles/9641878.html

[1460047-20180913192316882-1579012201.png]: /images/20210724/4f912e4e480c40d7b65778feb9ad51bf.png