题解：P4499 [CTSC2011] 无穷图的桥

inc1ude_c · 2024-04-12 19:18:31 · 题解

第一篇黑题题解，哪里讲的有错希望能指出。

Part -1

传说中搜不到题解的题（之一）。

但是科学上网后还是搜到了一篇 VFleaking 的题解，结果里面的图挂了看着相当吃力……搞了几天才做出来。

前置知识倒也不是太多，会使用并查集求出桥与边双连通分量就可以了。

请留下充足的时间与耐心来看这篇题解。

Part 0

首先有两个定义：对于一层图的边我们叫横边，对于连接相邻两层图的边我们叫竖边。

我们需要清楚这条事实：对于同一条边，要么一直是桥，要么一直不是桥，要么只在前若干层是桥。

这样我们就可以很方便地算贡献了：

1. 对于一条边，它一直是桥，则贡献为 \sum\limits_{i=0}^{+\infty}0.9^id=10d。

2. 对于一条边，它只在前 s 层是桥，则贡献为 10\times (1-0.9^{s})d。其中 s\ge 1。

Part 1

我们先搞定第一层。

我们要求的东西是：

• 两个并查集 \text{ufs1} 和 \text{ufs2}，分别管理第一层所有连通分量，和第一层所有边双连通分量。

这个可以在第一层（不包括竖边）上 DFS 一遍求出。

但我们还是要考虑竖边，于是我们考虑扫一遍竖边，求出这些东西：

这些东西可以揉在一起做，算法如下：

初始时 \text{bri1} 与 \text{bri2} 皆为真。

遍历所有竖边，当前遍历的竖边为 i，这时看 i 的左端点（简称 i.u）是否有没有被访问：

• 若没有，则 i.u 是一个连通块的根。对其 DFS，并且 \text{cctop}_{i.u} 就是 i。

• 若有，则找到 i.u 所在连通块的根，把 i.u 到这个根的 \text{cctop} 的左端点路径上的边双都合并一下。

rep(i,1,m2){
  if(!vis[e2[i].u])dfs(e2[i].u,0),cctop[e2[i].u]=i;
  else{
    int j=ufs1.find(e2[i].u);mpath(e2[i].u,e2[cctop[j]].u);
    bri2[i]=bri2[cctop[j]]=0;
  }
}

mpath 是将两点路径上的边双都合并并返回上面所有桥的 d 之和。可以在题解的在最后看到。

我们为什么要求出这些东西？为了求出第一层的每个连通分量通过竖边与哪些边双连通分量直接相连。

Part 2

在这之前先定义一些东西吧：

• 只考虑前 i 行，若第 i 行 u,v 之间有路，则 u,v 属于一个奇葩连通分量。
• 只考虑前 i 行，若第 i 行 u,v 之间有不经过桥的路，则 u,v 属于一个奇葩边双连通分量。
• 对于一个奇葩连通分量，如果它往下只对 1 个奇葩边双连通分量有连边，则它就是没存在感的。

这些定义都是沿用的 VFleaking 题解中的定义。orz VFleaking。

我们发现最开始 \text{ufs1} 和 \text{ufs2} 已经求出对于前 1 行的奇葩连通分量与奇葩边双连通分量。

考虑从第 i-1 行转移到第 i 行，奇葩连通分量与奇葩边双连通分量（即那两个并查集）有哪些变化。显然我们要对一些竖边分类讨论。

情况一：某第 i-1 行奇葩连通分量和某第 i 行奇葩边双连通分量间连有很多条边。

只需要保留一条就可以了，我们关心的是每个奇葩连通分量与哪些奇葩边双连通分量直接相连。

情况二：某第 i-1 行奇葩连通分量只和某第 i 行奇葩边双连通分量有边。

这就是我们上面定义的“没存在感的奇葩连通分量”。这里解释一下为什么是“没存在感的”：只与一个边双有边意味着不会有环，就不会发生合并，没有合并就不会对第 i 层有任何影响。

当然你可能有我最开始的这样的疑问：如果它们只有一条边相连，那这条边不就是桥吗？那能叫“没有任何影响”？注意我们是关心边在哪层就不是桥了，这点在 Part 0 就提到过。

情况三：某第 i-1 行奇葩连通分量和第 i 行某两个处于同一奇葩连通分量的奇葩边双连通分量有边。

合并边双，具体看图：

粗边指的是桥。

我们就是把两个路径上的边双合并，然后这些被合并的桥都不再是桥了，于是我们结算贡献，这也就是为什么 mpath 要返回桥的权值和。

情况四：某第 i-1 行奇葩连通分量和第 i 行某两个奇葩连通分量有边。