BZOJ2208: [Jsoi2010]连通数(tarjan bitset floyd)
程序员文章站
2022-04-28 14:03:46
题意 "题目链接" Sol 数据水的一批,$O(n^3)$暴力可过 实际上只要bitset优化一下floyd复杂度就是对的了($O(\frac{n^3}{32})$) 还可以缩点之后bitset维护一下连通性,然后对每个联通块之间的分别算,复杂度是$O(\frac{nm}{32})$(好像和上面的没 ......
题意
sol
数据水的一批,\(o(n^3)\)暴力可过
实际上只要bitset优化一下floyd复杂度就是对的了(\(o(\frac{n^3}{32})\))
还可以缩点之后bitset维护一下连通性,然后对每个联通块之间的分别算,复杂度是\(o(\frac{nm}{32})\)(好像和上面的没区别。。。)
上面代码是floyed
下面的是tarjan
// luogu-judger-enable-o2 #include<bits/stdc++.h> using namespace std; const int maxn = 2001; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n; char s[maxn]; bitset<maxn> f[maxn]; int main() { n = read(); for(int i = 1; i <= n; i++) { scanf("%s", s + 1); for(int j = 1; j <= n; j++) f[i][j] = (s[j] == '1' || (i == j)); } for(int k = 1; k <= n; k++) for(int i = 1; i <= n; i++) if(f[i][k]) f[i] = f[i] | f[k]; int ans = 0; for(int i = 1; i <= n; i++) ans += f[i].count(); cout << ans; return 0;; }
// luogu-judger-enable-o2 #include<bits/stdc++.h> using namespace std; const int maxn = 4001; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, dfn[maxn], low[maxn], tot, vis[maxn], col[maxn], siz[maxn], cnt, inder[maxn]; stack<int> s; char str[maxn]; bitset<maxn> f[maxn]; vector<int> v[maxn], e[maxn]; void tarjan(int x) { dfn[x] = low[x] = ++tot; vis[x] = 1; s.push(x); for(int i = 0; i < v[x].size(); i++) { int to = v[x][i]; if(!dfn[to]) tarjan(to), low[x] = min(low[x], low[to]); else if(vis[to]) low[x] = min(low[x], dfn[to]); } if(low[x] == dfn[x]) { int h; cnt++; do { h = s.top(); s.pop(); vis[h] = 0; col[h] = cnt; siz[cnt]++; }while(h != x); } } void topsort() { queue<int> q; for(int i = 1; i <= cnt; i++) { f[i][i] = 1; if(!inder[i]) q.push(i); } while(!q.empty()) { int p = q.front(); q.pop(); for(int i = 0; i < e[p].size(); i++) { int to = e[p][i]; f[to] |= f[p]; if(!(--inder[to])) q.push(to); } } int ans = 0; for(int i = 1; i <= cnt; i++) { for(int j = 1; j <= cnt; j++) { if(f[i][j]) ans += siz[i] * siz[j]; } } printf("%d\n", ans); } int main() { n = read(); for(int i = 1; i <= n; i++) { scanf("%s", str + 1); for(int j = 1; j <= n; j++) if(str[j] == '1' || (i == j)) v[i].push_back(j); } for(int i = 1; i <= n; i++) if(!dfn[i]) tarjan(i); for(int i = 1; i <= n; i++) { for(int j = 0; j < v[i].size(); j++) { int to = v[i][j]; if(col[to] != col[i]) e[col[to]].push_back(col[i]), inder[col[i]]++; } } topsort(); return 0;; }
上一篇: 关于类的几点说明