专栏首页wymP3469 [POI2008]BLO-Blockade tarjan割点

P3469 [POI2008]BLO-Blockade tarjan割点

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/qq_41603898/article/details/102146708

题意:有n个点m条无向边,每个点要拜访其他所有点,总共有n*(n-1)次拜访次数。保证图联通,问禁止通行某个点后一共会少多少次拜访次数。输出n行,每行代表 i点禁止通行会减少的拜访次数。

解:如果这个点不影响图的联通性,则答案为2*(n-1),也即他不能到所有的n-1个点,n-1个点也不能到达他。

如果影响图的联通性,也就是割点,则答案再加上各个分量累乘之和,采用tarjan求割点时,由于是像树一样遍历,考虑子树之间对答案的贡献和所有子树之和对除子树外的点的贡献。求出的是单向的输出*2

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 100005;
int n,m,x,y,tot,tim;
int dfn[N],low[N],size[N],head[N],cut_point[N];
ll ans[N];
struct Edge{
	int to,nxt;
}edge[1000005];
void add(int x,int y){
	tot++;
	edge[tot].to = y;
	edge[tot].nxt = head[x];
	head[x] = tot;
}
int tarjan(int now){
	int z = 0;size[now] = 1;
	dfn[now] = low[now] = ++tim;
	for(int i=head[now];i;i=edge[i].nxt){
		int t = edge[i].to;
		if(!dfn[t]){
			tarjan(t);
			size[now]+=size[t];
			low[now] = min(low[now],low[t]);
			if(dfn[now]<=low[t]){
				ans[now]+=(ll)z*size[t];
				z+=size[t];
			}
		}else low[now] = min(low[now],dfn[t]);
	}
	ans[now]+=(ll)z*(n-z-1);
}
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d %d",&x,&y);
		add(x,y);
		add(y,x);
	}
	tarjan(1);
	for(int i=1;i<=n;i++){
		printf("%lld\n",(ans[i]+n-1)<<1);
	}
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

推荐阅读

  • 智能监控时代-监控建设之道

    在正式阅读本文之前,我们先思考一个问题-几乎每个IT公司都有一套自己的运维监控系统,每家公司的运维都在做监控系统,而似乎每家都在面临一个问题,监控系统不好用,不能解决实际的监控问题,有没有更好的监控系统呢?答案是有的,本文将为您揭晓谜底。

    腾讯蓝鲸助手
    云监控运维解决方案运维
  • 虚拟机统一管理建设心得分享

    在IT运维体系中,虚拟机作为最常见的底层资源,随着企业的规模逐渐扩大,虚拟机的数量也在快速增长,以往运维人员在处理虚拟机的管理问题时,由于规模并不大,通常采取人工方式进行虚拟机的安全管理。

    腾讯蓝鲸助手
    运维运维解决方案虚拟化
  • MySQL Case-show processlist Sending to client状态详解

    今天客户脱敏机器,访问MySQL数据库查询数据,show processlist状态一直处于Sending to client状态,时间持续了1.5h还没有结束,那么一直处于这个状态具体是在做什么呢?如何缩短这个状态时间呢?今天我们来看下这个案例,同时我也在自己的测试环境模拟了测试下。

    姚崇
    云数据库 MySQL数据库网络流日志
  • MySQL Case-通过optimizer_trace看MySQL优化器行为

    我们在日常维护数据库的时候,如果遇到慢语句查询的时候,我们一般会怎么做?执行EXPLAIN去查看它的执行计划?是的。我们经常会这么做,然后看到执行计划展示给我们的一些信息,告诉我们MySQL是如何执行语句的。但是,执行计划往往只给我们带来了最基础的分析信息,比如是否有使用索引,还有一些其他供我们分析的信息,比如使用了临时表、排序等等。

    姚崇
    MySQL数据库云数据库 MySQL
  • 脚本更新tke集群中CLB类型Ingress证书

    通常我们在tke里面进行7层服务暴露,可以用nginx ingress和clb类型的ingress,如果你用的clb类型ingress,需要在tke这边用secret配置腾讯云上的证书,当你的证书过期或者不存在,配置错误时,会导致ingress同步规则到clb失败,从而导致访问域名出现异常,这个时候需要正确在tke这边更新ingress的证书id才能解决这个问题。

    聂伟星
  • Oceanus实践-从0到1开发MySQL-cdc到ES SQL作业

    实时及未来,最近在腾讯云Oceanus进行实时计算服务,以下为mysql到flink到ES实践。分享给大家~

    吴云涛
    流计算服务 Oceanus大数据解决方案
  • 快速搭建一个下载站:详解Linux上部署h5ai实现目录映射

    H5AI,其实全称是:HTML5 Apache Index。最初是用来在Apache Web服务器上,完成资源映射,但是后来适配到Nginx等其他平台。使用H5AI的效果:

    Mintimate
    轻量应用服务器 LighthouseLinuxPHP网站建设
  • 网络基本概念服务、协议、进程、端口之间的关系。

    网络通信中路由器是必不可少的设备,因为随着网络需求的发展,不管是企业IDC机房内还是普通用户家中的网络连接都需要使用到路由器,所以我这里大致的描述下路由器的工作原理,这里是一般针对企业IDC机房内的描述,用户家中的路由器也相当于是一个和互联网通信的网关设备,因为用户家中一般是无需进行子网划分的。

    子沐u
    私有网络TCP/IPhttpsCentOSLinux
  • 在腾讯云上安装和使用 JuiceFS 存储

    JuiceFS 是一个云原生的企业级开源共享文件系统,广泛应用于大数据、企业级数据共享、Kubernetes 容器编排、AI 机器学习、Web 服务和内容管理、数据容灾备份等场景。它将对象存储作为大容量本地磁盘使用,为云上应用提供近乎无限的存储空间。与此同时,得益于其独特的技术架构,在存储和处理大规模数据时,性能通常高于本地存储。

    谈笑有Herald
    云服务器对象存储云数据库 Redis私有网络访问管理
  • 高吞吐实时事务数仓方案调研 flink kudu+impala hbase等

    需要说明的是,source表、sink表并不代表在oceanus中真的创建了类似数据库的真实物理表,实际上source表、sink表均是逻辑表,它只是通过业务填写的配置项映射到真实的数据源、目的地。

    大鹅
    弹性 MapReduceHBase流计算服务 OceanusJava云服务器

扫码关注云+社区

领取腾讯云代金券