博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
BZOJ2208:[JSOI2010]连通数——题解
阅读量:6259 次
发布时间:2019-06-22

本文共 1839 字,大约阅读时间需要 6 分钟。

 floyd压位是神马东西……

 我们tarjan缩点之后反向拓扑就可以记录联通块可达状态,然后可达就sz[i]*sz[j]就行了。

#include#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;typedef long long ll;const int N=2005;struct edge{ int cnt,head[N]; int to[N*N],nxt[N*N]; edge(){ cnt=0;memset(head,0,sizeof(head)); } inline void add(int u,int v){ to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt; }}e,f;char s[N];int sz[N],dfn[N],low[N],to[N],t,l;bool inq[N];stack
q;void tarjan(int u){ dfn[u]=low[u]=++t; q.push(u);inq[u]=1; for(int i=e.head[u];i;i=e.nxt[i]){ int v=e.to[i]; if(!dfn[v]){ tarjan(v); low[u]=min(low[u],low[v]); }else if(inq[v]){ low[u]=min(low[u],dfn[v]); } } if(dfn[u]==low[u]){ int v;l++; do{ v=q.top();q.pop();inq[v]=0; to[v]=l;sz[l]++; }while(v!=u); }}int deg[N];queue
que;bitset
d[N];void topu(int n){ for(int i=1;i<=l;i++){ d[i][i]=1; if(!deg[i])que.push(i); } while(!que.empty()){ int u=que.front();que.pop(); for(int i=f.head[u],v;i;i=f.nxt[i]){ deg[v=f.to[i]]--; d[v]|=d[u]; if(!deg[v])que.push(v); } }}int main(){ int n;scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%s",s+1); for(int j=1;j<=n;j++) if(s[j]-'0')e.add(i,j); } for(int i=1;i<=n;i++) if(!dfn[i])tarjan(i); for(int u=1;u<=n;u++){ for(int i=e.head[u];i;i=e.nxt[i]){ int v=e.to[i]; if(to[u]==to[v])continue; bool flag=1; for(int j=f.head[to[v]];j&&flag;j=f.nxt[j]) if(f.to[j]==to[u])flag=0; if(flag)f.add(to[v],to[u]),deg[to[u]]++; } } topu(l); int ans=0; for(int i=1;i<=l;i++) for(int j=1;j<=l;j++) if(d[i][j])ans+=sz[i]*sz[j]; printf("%d\n",ans); return 0;}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者:luyouqi233。               +

+欢迎访问我的博客: +

+++++++++++++++++++++++++++++++++++++++++++

转载于:https://www.cnblogs.com/luyouqi233/p/9210693.html

你可能感兴趣的文章
Oracle SID爆破工具SidGuess
查看>>
批处理常用命令总结2
查看>>
解读ASP.NET 5 & MVC6系列(9):日志框架
查看>>
MyEclipse生成WAR包并在Tomcat下部署发布(转发)
查看>>
Android -- 自定义View小Demo,绘制钟表时间(一)
查看>>
信息检索Reading List
查看>>
JavaWeb_JavaEE_命名规则
查看>>
申小雨命案审理延期至3月5日 警方将翻译嫌犯口供
查看>>
自动精简配置&重复数据删除核心技术点及其经济效应探究
查看>>
cncert网络安全周报35期 境内被植入后门的政府网站112个 环比上涨24.4%
查看>>
物联网到底是不是泡沫,且看英特尔交出的答案
查看>>
IPv6太落后了:中国加速服务器援建
查看>>
安防大数据应用国家工程实验室在乌鲁木齐成立
查看>>
物理引擎中velocity的单位是个什么鬼?
查看>>
[译] 全新 Android 注入器 : Dagger 2 (二)
查看>>
为什么要评审代码?
查看>>
小程序开发前的准备工作之【深入封装Component】
查看>>
AFN3.0源码解析
查看>>
oracle的drop命令
查看>>
设计与梳理企业二级流程的路线方法
查看>>