[UVA1660]电视网络Cable TV Network

题目链接

不得不说,网络流的题目其实实现起来都是套模板,但是要想到就很困难。

很多人学了最小割之后就来切这道“裸题”,数据范围小,还没要求输出具体方案,太简单了!

但是最小割是适用于有向图,而且是边集,但是这道题是要我们找出点的个数,而且是无向图。

在看这篇题解的时候默认你知道“最大流最小割定理

我们先来着手解决第一个问题:无向图转化成有向图。

由于这道题是关于图的连通性的问题,因此转化出来的有向图和原图连通性不变

如上图,我们可以将原来的图的每个点,拆成两个点x,x’(图中的点不包括源点和汇点),在它们之间连容量为1的有向边。对于原来的边(x,y),我们可以转化成(x’,y)和(y’,x)这两条有向边,容量为\(\infty\)

这样做显然连通性不变。

而且,我们发现,在原图中,如果删去y点,x与z就不连通了;

在转换图中,如果删去(y,y’)那么x与z也是不连通的;

于是我们可以将问题转化为:在转化后图中,至少删掉多少条权值为1的边才能使图不连通;

这就是一个典型的最小割问题,由于其他边权值都是 \infty ,而图中最大流量为N-2,因此求最小割的时候贡献答案的一定是权值为1的边。

代码

Q&A

对于上面有些问题没弄懂的可以看这里

Q1:为什么最大流量是N-2

A:你可以想一下最大流量的情况,就是整个图分3层,第一层为源点,第三层为汇点,第二层有N-2个点,每个点流量都是1;

欢迎提问~

发表评论

电子邮件地址不会被公开。 必填项已用*标注