草庐IT

[JSOI2010]连通数

ziyistudy 2023-04-19 原文

传送地址：https://www.luogu.com.cn/problem/P4306

题目描述

度量一个有向图连通情况的一个指标是连通数，指图中可达顶点对个的个数。

如图

顶点 11 可达 1, 2, 3, 4, 51,2,3,4,5

顶点 22 可达 2, 3, 4, 52,3,4,5

顶点 33 可达 3, 4, 53,4,5

顶点 4, 54,5 都只能到达自身。

所以这张图的连通数为 1414。

给定一张图，请你求出它的连通数

 

题解

这题打了半天，发现用dfs或者bfs都是会TLE

于是就想采用另一种方法：bitset

 这样我们就可以用0代表不能到达，1代表可以到达

最后对对可以到的的进行求和即可

另外，关于bitset的使用以及函数调用，请参考：https://cplusplus.com/reference/bitset/bitset/?kw=bitset

其他就不多赘述了。

AC代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N=2e3+5;
 4 bitset<N> B[N];//给每一个节点建立bitset
 5 int main()
 6 {
 7     int n;cin>>n;
 8     for(int i=1;i<=n;i++){
 9         string s;cin>>s;
10         for(int j=1;j<=n;j++){
11             if(s[j-1]=='1'||i==j) B[i][j]=1;
12                         //能到这个节点或者自己
13         }
14     }
15     for(int i=1;i<=n;i++){
16         for(int j=1;j<=n;j++){
17             if(B[j].test(i)) B[j]|=B[i];
18                         //如果j可以到达i，则i可以到达的所有节点j都能到达
19                        //这里的“|”在此不在讲述
20         }
21     }
22     int ans=0;
23     for(int i=1;i<=n;i++) ans+=B[i].count();//计算有多少个1
24     cout<<ans<<endl;
25     return 0;
26 }

 

JSOI2010spancolorstyleC++

有关[JSOI2010]连通数的更多相关文章

  1. ruby-on-rails - 我现在(2010 年 1 月)应该使用哪个版本的 Ruby？ - 2

    我有1.8.6附带的VanillaMacOSXLeopard。我是RoR的新手，所以会学习网上的教程。在使用更高版本的Ruby时，我是否可能会发现遵循它们的问题？我目前正在查看提到1.8.6和1.8.7的这个-http://www.railstutorial.org/book 最佳答案 RoR教程对两者都适用，但如果您正在学习Ruby，则应该学习1.9。Rails3将不支持1.8.6，所以我会选择1.8.7或1.9。我还推荐使用RVM在Ruby版本之间切换。 关于ruby-on-rail

  2. ruby-on-rails - Railscasts 第 362 集 - 导出到 Excel : How to avoid the warning message given by Excel 2010 when opening the file? - 2

    当使用RyanBates的Railscasts第362集关于导出到Excel(https://github.com/railscasts/362-exporting-csv-and-excel)的示例应用程序时，我注意到Excel2010(在Windows上)在打开.xls文件时给我一条警告消息我使用“下载为Excel”链接下载的文件。警告内容如下:“您尝试打开的文件...的格式与文件扩展名指定的格式不同。打开文件前请确认文件未损坏且来源可靠。是否要打开现在存档吗？”当我单击"is"时，我可以很好地打开文件。在使用Excel2011(在Mac上)时，我什至没有收到警告消息。但我希望能够

  3. IGH主站通信测试csp模式（DC同步 preemrt）连通一从站并实现控制 - 2

    IGH主站通信测试linuxcnc配置基础机器人控制LinuxCNC与EtherCAT介绍&&PDO&SDO，搭建环境步骤需要配置IGH主站的查看这篇文章linux系统学习笔记7——一次性安装igh-ethercat主站CSP模式DC同步方式preemrt实时补丁直接上代码，这部分是直接控制使用csp模式控制一个从站运动使能后直接运动，10s，每秒607a（目标位置）增加100.注意：急停按下ESC代码分为两部分，一个是通信线程主要负责和伺服通信，使能伺服，读取和写入寄存器值。第二个是操作线程，负责修改位置的值，和监控按键。使用此代码，首先根据手册1.修改PDO条目，要和自己的伺服一致2.修改

  4. javascript - Visual Studio 2010 阻止对某些文件进行 JScript 调试 - 2

    是否可以防止Javascript调试器进入某些文件？我特别不希望它在JqueryJavaScript文件中抛出异常时中断:其他第3方缩小文件也是如此……每次出现运行时错误时，它都会显示通知并打开文件。中断执行并打开缩小的文件并不能帮助我找到错误的原因。 最佳答案 某些原因导致了错误，您可能不应该忽略它。我建议切换到调试(未缩小)脚本并弄清楚错误到底是什么。一旦出现错误，如果您无法解决，请将其发布到stackoverflow上，我相信有人能够为您提供更多帮助。尝试通过jslint运行您的自定义脚本，看看是否存在任何明显的问题。http

  5. javascript - Visual Studio 2010 : Javascript Highlighting - 2

    我将VisualStudio2010与VS.PHP结合使用。当我编写或打开一个javascript文件时，它没有突出显示并且智能感知不工作。我看到的都是纯文本。VS似乎没有“识别”javascript文件。当我手动命令js文件在脚本编辑器中打开时(在工具>选项>文本编辑器>文件扩展名中)，没有任何变化。荧光笔(在“工具”>“选项”>“环境”>“工具和颜色”中)已正确设置。你有什么想法我怎样才能突出显示？谷歌什么也没说。 最佳答案 您可能在安装VisualStudio时删除了“WebDeveloper2010”组件。或者您正在使用其中

  6. javascript - 让 JSLint 打破 visual studio 2010 中的构建 - 2

    我已将JSLint(http://javascriptlint.com)集成到我的构建后项目中-但似乎无法在出现错误/警告时使构建失败？目前JSLint是从一个在构建后执行的.bat文件中运行的如果遇到错误/警告，我可以传入一个参数来告诉JSLint使构建失败吗？先谢谢大家 最佳答案 JSLintextensionforVS2010有一个选项可以在错误列表中自动显示JSLint警告。此外，您可以在构建时运行JSLint并在违反规则时取消构建。或者，如果您想通过批处理脚本继续运行JSLint，您可以强制MSBuild根据脚本的返回退出

  7. javascript - Sharepoint 2010 客户端对象模型 - 获取当前列表的名称 - 2

    我正在尝试为Sharepoint2010中的功能区菜单创建一个简单的自定义操作按钮。我想保持它的通用性，所以不要对库名称等进行硬编码。如何找到当前正在查看的列表的名称？我想这是可能的，而不必从Url中解析它。非常感谢! 最佳答案 这花了一些时间，但我最终找到了答案。您可以使用Javascript获取列表的ID://GettheIdofthelistvarlistId=SP.ListOperation.Selection.getSelectedList(); 关于javascript-Sh

  8. javascript - 使用 Visual Studio 2010 时禁用 IE9 Javascript 调试器 - 2

    在IE9下使用VisualStudio时，有没有办法禁用javascript调试？ 最佳答案 如果单击工具(Alt+X)按钮，则单击Internet选项菜单项。在Advanced选项卡和Browsing类别中:检查禁用脚本调试(InternetExplorer)这应该禁用Javascript调试器 关于javascript-使用VisualStudio2010时禁用IE9Javascript调试器，我们在StackOverflow上找到一个类似的问题： htt

  9. javascript - Visual Studio 2010 中缺少 javascript 智能感知 - 2

    我很高兴在VisualStudio2010中看到javascriptintellisense，但在下面的代码中，我没有通过它看到特定对象内的所有内容if(document.images[i].parentNode.tagName=="A"“parentNode”没有出现在intellisense中，这让我觉得我输入了错误的代码，但它确实存在并且VisualStudio没有显示它..如何解决这个问题？更新进度:使用NetBeans7.1，它对我的​​JavaScript没有帮助，为VStudio2010安装了JScriptExtensions，在js编辑方面有一些改进，但在Javascr

  10. javascript - 查找无向图的所有连通分量 - 2

    我有一个对象列表(无向边)，如下所示:pairs=[pair:["a2","a5"],pair:["a3","a6"],pair:["a4","a5"],pair:["a7","a9"]];我需要在单独的组中找到所有组件(连接的节点)。所以从给定的对中我需要得到:groups=[group1:["a2","a5","a4"],group2:["a3","a6"],group3:["a7","a9"]];我实际上在这里阅读了一些答案并用谷歌搜索了这个，这就是我如何了解到这被称为“在图中查找连接的组件”，但是找不到任何示例代码。我在Node.js上使用JavaScript，但任何其他语言的

随机推荐