「BZOJ2208」[JSOI2010] 连通数
Description
Input
输入数据第一行是图顶点的数量，一个正整数N。 接下来N行，每行N个字符。第i行第j列的1表示顶点i到j有边，0则表示无边。
Output
输出一行一个整数，表示该图的连通数。
Sample Input
3
010
001
100
010
001
100
Sample Output
9
HINT
对于100%的数据，N不超过2000。
题解
据说此题暴力是可过的，复杂度O（nm）
正解似乎是先缩点完然后递推
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,cnt,scc,top,ind,lim,ans; int head[2005],h[2005],r[2005]; int dfn[2005],low[2005],st[2005]; int belong[2005],hav[2005]; bool inst[2005]; int mark[2005][85]; char ch[2005]; struct data{int to,next;}e[4000005],ed[4000005]; void insert(int u,int v) {e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;} void ins(int u,int v) {ed[++cnt].to=v;ed[cnt].next=h[u];h[u]=cnt;r[v]++;} void tarjan(int x) { int now=0; dfn[x]=low[x]=++ind; st[++top]=x; inst[x]=1; for(int i=head[x];i;i=e[i].next) if(!dfn[e[i].to]) {tarjan(e[i].to);low[x]=min(low[x],low[e[i].to]);} else if(inst[e[i].to])low[x]=min(low[x],dfn[e[i].to]); if(low[x]==dfn[x]) { scc++; while(now!=x) { now=st[top--]; inst[now]=0; belong[now]=scc; hav[scc]++; } } } void rebuild() { cnt=0; for(int i=1;i<=n;i++) for(int j=head[i];j;j=e[j].next) if(belong[i]!=belong[e[j].to]) ins(belong[e[j].to],belong[i]); } void solve() { top=0;int now; for(int i=1;i<=n;i++) mark[belong[i]][i/30+1]|=(1<<(i%30)); for(int i=1;i<=scc;i++) if(!r[i])st[++top]=i; while(top) { now=st[top];top--; for(int i=h[now];i;i=ed[i].next) { for(int j=1;j<=lim;j++) mark[ed[i].to][j]|=mark[now][j]; r[ed[i].to]--; if(!r[ed[i].to])st[++top]=ed[i].to; } } } int main() { scanf("%d",&n);lim=n/30+1; for(int i=1;i<=n;i++) { scanf("%s",ch); for(int j=1;j<=n;j++) if(ch[j-1]-'0')insert(i,j); } for(int i=1;i<=n;i++) if(!dfn[i])tarjan(i); rebuild(); solve(); for(int i=1;i<=scc;i++) for(int j=1;j<=n;j++) if((mark[i][j/30+1])&(1<<(j%30))) ans+=hav[i]; printf("%d",ans); return 0; } |
计数器 9787993
OI 课件=>
OI 课件=>
顺便问一下这个模数要怎么取(怎么得来的),比如数据范围是5000又该取多少
所以闭包到底是什么
后面那东西是叫传递闭包吧。。不过hzwer学长都说他是递推了就递推吧
传递闭包。。唔我理解的传递闭包似乎是用floyd。。。不过你这么一说倒是想起来了