UVA1660电视网络CableTVNetwork[拆点+最小割]

题意翻译

题目大意&＃xff1a; 给定一个n(n <&＃61; 50)个点的无向图&＃xff0c;求它的点联通度。即最少删除多少个点&＃xff0c;使得图不连通。

解析

网络瘤拆点最小割。

定理

最大流\(&＃61;\)最小割

感性地理解&＃xff08;口胡&＃xff09;一下&＃xff1a;首先显然最大流\(<&＃61;\)割&＃xff0c;而根据最大流定义&＃xff0c;最小割恰恰就是要恰好割断最大流经过的所有最窄流量的边集&＃xff0c;就能恰好使得源点和汇点不连通&＃xff0c;即最大流\(&＃61;\)最小割。

至于具体的证明&＃xff0c;我也不知道。

拆点

一般来说&＃xff0c;正常的拆点有两个作用&＃xff1a;

1. 在不改变原图连通性的情况下&＃xff0c;将点权转化为边权。
2. 通过化点为边&＃xff0c;限制通过某点的流量。

对于无向图和有向图&＃xff0c;一般意义上的拆点做法是相同的。

一般做法&＃xff1a;以有向图为例&＃xff0c;对于原图中的一个点对\((x,y)\)&＃xff0c;且有一条有向边\(c(x,y)\)。我们将其分别拆成两个点\(x,x&＃39;,y,y&＃39;\)&＃xff0c;然后\(x\rightarrow x&＃39;,y\rightarrow y&＃39;\)这样连接有向边&＃xff0c;如果原来的点有点权那么将有向边的边权赋值为点权&＃xff0c;如果没有点权则赋值为1。对于原图存在的有向边&＃xff0c;连接\(x&＃39;\rightarrow y\)。

对于无向边&＃xff0c;我们再连一条边\(y&＃39;\rightarrow x\)即可。

那么对于本题&＃xff0c;显然是一个求最少割点&＃xff0c;我们转化为拆点最大流做。

注意可能有多组数据。

参考代码

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include