UVa 1660 Cable TV Network - 指南

题目描述

给定一个双向连接的有线电视网络，网络由中继器（节点）和电缆（边）组成。网络连通的定义是：任意两个节点之间至少存在一条路径。安全系数$f$的定义如下：

1. 如果无论删除多少个节点（只要不全部删除），网络都保持连通，则$f=n$（$n$为节点数）。
2. 否则，$f$等于能够使网络断开的最小删除节点数。

注意：

• 空网络（$n=0$）或单节点网络（$n=1$）视为连通。
• 输入数据保证正确，节点数$n\le 50$。

题目分析

本题要求计算一个无向图的节点连通度（$\text{vertex connectivity}$），即最少需要删除多少个节点才能使图变得不连通。

关键点分析

1. 特殊情况处理：

   • 如果 $n\le 1$，根据定义，网络是连通的，安全系数$f=n$。
   • 如果原图本身不连通，则删除$0$个节点就不连通了，所以$f=0$。

2. 一般情况：

   • 我们得找到最小的$k$，使得存在一个大小为$k$的节点集合，删除这些节点后图变得不连通。
   • 这等价于图的节点连通度障碍。

算法思路

我们可以利用最大流最小割定理来求解节点连通度：

1. 拆点法：

   • 将每个节点 $u$拆成两个节点：$u_{in}$ 和 $u_{out}$。
   • 在 $u_{in}$ 和 $u_{out}$之间连一条容量为$1$的边，表示删除该节点的代价。
   • 对于原图中的边$(u,v$