UVa 1660 Cable TV Network

题目描述

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

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

注意：

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

题目分析

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

关键点分析

1. 特殊情况处理：
   • 如果 n≤1n \leq 1n≤1，根据定义，网络是连通的，安全系数 f=nf = nf=n。
   • 如果原图本身不连通，则删除 000 个节点就不连通了，所以 f=0f = 0f=0。
2. 一般情况：
   • 我们需要找到最小的 kkk，使得存在一个大小为 kkk 的节点集合，删除这些节点后图变得不连通。
   • 这等价于图的节点连通度问题。

算法思路

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

1. 拆点法：
   • 将每个节点 uuu 拆成两个节点：uinu_{in}uin​ 和 uoutu_{out}uout​。
   • 在 uinu_{in}uin​ 和 uoutu_{out}uout​ 之间连一条容量为 111 的边，表示删除该节点的代价。
   • 对于原图中的边 (u,v)(u, v)(u,v

《UVa 1660 Cable TV Network》 是转载文章，点击查看原文。