【BZOJ 2208】 [Jsoi2010]连通数

2208: [Jsoi2010]连通数Time Limit:20 SecMemory Limit:512 MBSubmit:1431Solved:585[Submit][Status][Discuss]Description

Input

输入数据第一行是图顶点的数量，一个正整数N。 接下来N行，每行N个字符。第i行第j列的1表示顶点i到j有边，0则表示无边。

Output

输出一行一个整数，表示该图的连通数。

Sample Input

3010 001 100

Sample Output

9

HINT

对于100%的数据，N不超过2000。

Source

第一轮

tarjan缩点+拓扑排序+状态压缩

首先缩点，图成为拓扑图。

然后用f[i]表示i与其他点的连通情况（用bitset），f[i][j]=1表示i可以到达j。

按照拓扑序，将i能连到的点j对的f[j]对f[i]整体取或，表示i能到的j也能到。

注意，这样做得到的连通情况是与原图相反的，求出i能到j说明在原图中j能到i。

#include <iostream>#include <algorithm>#include <cstring>#include <cstdio>#include <cmath>#include <cstdlib>#define M 2000+5#include <stack>#include <bitset>#include <queue>using namespace std;queue<int> q;stack<int> s;char S[M];bitset<M> f[M];int h[M],scc[M],H[M],Tot,tot,du[M],sccno[M],pre[M],lowlink[M];int n,m,dfs_clock,scc_cnt,v[M][M];struct edge{int y,ne;}e[4000005],E[4000005];void addedge(int x,int y){e[++tot]=(edge){y,h[x]};h[x]=tot;du[y]++;}void Addedge(int x,int y){E[++Tot]=(edge){y,H[x]};H[x]=Tot;}void dfs(int x){pre[x]=lowlink[x]=++dfs_clock;s.push(x);for (int i=H[x];i;i=E[i].ne){int y=E[i].y;if (!pre[y]){dfs(y);lowlink[x]=min(lowlink[x],lowlink[y]);}else if (!sccno[y])lowlink[x]=min(lowlink[x],pre[y]);}if (lowlink[x]==pre[x]){scc_cnt++;scc[scc_cnt]=0;for (;;){int k=s.top();s.pop();sccno[k]=scc_cnt;scc[scc_cnt]++;if (k==x) break;}}}void Findscc(){dfs_clock=scc_cnt=0;for (int i=1;i<=n;i++)if (!pre[i])dfs(i);}void Rebuild(){for (int x=1;x<=n;x++)for (int i=H[x];i;i=E[i].ne){int sx=sccno[x],sy=sccno[E[i].y];if (sx!=sy&&!v[sx][sy])addedge(sx,sy),v[sx][sy]=1;}}void Topsort(){for (int i=1;i<=scc_cnt;i++)f[i][i]=1;for (int i=1;i<=scc_cnt;i++)if (!du[i]) q.push(i);while (!q.empty()){int x=q.front();q.pop();for (int i=h[x];i;i=e[i].ne){int y=e[i].y;du[y]–;f[y]=f[y]|f[x];if (!du[y]) q.push(y);}}}int main(){scanf("%d",&n);for (int i=1;i<=n;i++){scanf("%s",1+S);for (int j=1;j<=n;j++)if (i!=j&&S[j]=='1')Addedge(i,j);}Findscc();Rebuild();Topsort();int ans=0;for (int i=1;i<=scc_cnt;i++)for (int j=1;j<=scc_cnt;j++)if (f[i][j])ans+=(scc[i]*scc[j]);printf("%d\n",ans);return 0;}

感悟：

一开始这道题RE不止，因为定义M时：#define M 2000+5，而在边中用到M*M，，这样的计算结果是2000+5*2000+5。。自然就RE了

友谊之花、爱情之树、以及遗憾之泪！