洛谷P4003 无限之环(infinityloop)(网络流,费用流)by hjt

发布于 2018-01-31  12 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:洛谷P4003 无限之环(infinityloop)(网络流,费用流)by hjt

洛谷题目传送门
(题目顺便附在了下方)

思路分析

表示这是一道思维神题。。。。。。

有人第一眼看上去觉得这要跑费用流吗?

然而只要会建图,剩下的就是套模板的事了。

我们这样来理解。对于每个方格上的水管的每一个支管,有且仅有一个其它方格上的支管与其相连,这样就不会漏水了。用网络流知识表述,就是每个支管容量只能为1,且全都要满流,于是跑最小费用可行流

然而即使产生了最优情况,整个管网也不一定是一整个联通块,而可能被分成若干块。因此,怎样强制使每两个相邻的方格上都产生流量呢?就要把源汇点连到每个格子上。而且,还要对每个格点染色,相邻的两个格点,一个连源点,一个连汇点。具体的实现,就要利用格点行列坐标和的奇偶性来判断。

而产生的费用呢?当然是旋转造成的啦!真正的思维就体现在这里了。因为旋转还会造成接触点的变化,所以肯定是要拆点的,一个方格拆成五个点,上下左右中。。。。。。中间点连上源/汇点,并根据支管情况向四周连容量1,费用0的边。四周视作接触点,与对应相邻的另一个接触点连容量1,费用0的边。讨论相邻两个方格格因旋转而产生的有费用的连边,实在是太难了。。。。。。猛然发现,所有的情况,其实只需要在内部进行转化就好了。

所有的方格,我们大致分成以下几类进行讨论。

第一种:射线型

这种好办。射线指向上面,那么就让左、下、右接触点直接连接上接触点。左,右连上去,表示只要转90度,所以费用为1。下面连上去费用为2

第二种:直角型

这种理解起来就有难度了。如果顺时针转90度,会变成这样

相当于原来连上接触点的支管连到了下面,那么上与下建一条容量为1,费用为1的边。同样的道理,逆时针转90度,左与右建一条容量为1,费用为1的边。再来讨论转180度,这时候,会通过已有的边由左、下直接转移到右、上,费用加起来正好是2,所以不用连更多边了。

第三种:T字型

像前面一样讨论,也可以建边。从下向左、右各建一条容量为1,费用为1的边,向上建一条费用为2的边。这里就留给读者自己思考啦。


以上三种情况,每一种都有4个形状,但连边方法都是一样的。
还有直线型,十字型和空的,要么不能转,要么转了没意义,就不用内部建边了。

下面贴代码

附题目

题目描述

曾经有一款流行的游戏,叫做 Infinity Loop,先来简单的介绍一下这个游戏:
游戏在一个 n ∗ m 的网格状棋盘上进行,其中有些小方格中会有水管,水管可能在格子某些方向的边界的中点有接口,所有水管的粗细都相同,所以如果两个相邻方格的共边界的中点都有接头,那么可以看作这两个接头互相连接。水管有以下 15 种形状:
4003-1

游戏开始时,棋盘中水管可能存在漏水的地方。
形式化地:如果存在某个接头,没有和其它接头相连接,那么它就是一个漏水的地方。
玩家可以进行一种操作:选定一个含有非直线型水管的方格,将其中的水管绕方格中心顺时针或逆时针旋转 90 度。
直线型水管是指左图里中间一行的两种水管。
现给出一个初始局面,请问最少进行多少次操作可以使棋盘上不存在漏水的地方。

输入输出格式

输入格式:

第一行两个正整数 n, m,代表网格的大小。
接下来 n 行每行 m 个数,每个数是 [0,15] 中的一个,你可以将其看作一个 4 位的二进制数,从低到高每一位分别代表初始局面中这个格子上、右、下、左方向上是否有水管接头。
特别地,如果这个数是 0 ,则意味着这个位置没有水管。
比如 3(0011(2)) 代表上和右有接头,也就是一个 L 型;
而 12(1100(2)) 代表下和左有接头,也就是将 L 型旋转 180 度。

输出格式:

输出共一行,表示最少操作次数。如果无法达成目标,输出-1.

输入输出样例

输入样例#1:

输出样例#1:

输入样例#2:

输出样例#2:

输入样例#3:

输出样例#3:

说明

【样例 1 解释】

样例 1 棋盘如下
旋转方法很显然,先将左上角虚线方格内的水管顺时针转 90 度

然后右下角虚线方格内的水管逆时针旋转 90 度,这样就使得水管封闭了

【样例 2 解释】

样例 2 为题目描述中的第一张图片,无法达成目标。

【样例 3 解释】

样例 3 为题目描述中的第二张图片,将除了中心方格以外的每个方格内的水管都转 180 度即可。

闲话

小蒟蒻来SYCstudio.com签下到。。。。。。
对这里清爽的界面风格表示强烈资磁!!!

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:洛谷P4003 无限之环(infinityloop)(网络流,费用流)by hjt


或许前方只有...伸手不见五指的夜路,即使如此,我还是要充满信心、继续向前,相信星星的光芒...多少会照亮前方的道路,走吧!我们踏上旅程吧!