AC. 梦想

frank_c1

[BZOJ 2502] 清理雪道

发布于2016年03月21日 | 暂无评论 | 806阅读 | 有上下界网络流

题目描述

滑雪场坐落在FJ省西北部的若干座山上。

从空中鸟瞰,滑雪场可以看作一个有向无环图,每条弧代表一个斜坡(即雪道),弧的方向代表斜坡下降的方向。

你的团队负责每周定时清理雪道。你们拥有一架直升飞机,每次飞行可以从总部带一个人降落到滑雪场的某个地点,然后再飞回总部。从降落的地点出发,这个人可以顺着斜坡向下滑行,并清理他所经过的雪道。

由于每次飞行的耗费是固定的,为了最小化耗费,你想知道如何用最少的飞行次数才能完成清理雪道的任务。

输入格式

输入文件的第一行包含一个整数n\;(2 \le n \le 100) – 代表滑雪场的地点的数量。接下来的n行,描述1~n号地点出发的斜坡,第i行的第一个数为m_i\;(0 \le m_i \lt n) ,后面共有m_i个整数,由空格隔开,每个整数a_{ij}互不相同,代表从地点i下降到地点a_{ij}的斜坡。每个地点至少有一个斜坡与之相连。

输出格式

输出文件的第一行是一个整数k – 直升飞机的最少飞行次数。

题目解析

分析题目条件,发现这道题很特殊。每条边至少经过一次,也即流量至少为1。这让我们想到了有上下界网络流。

根据题目条件,可以这样建模:

1.建源ss向所有点连下界为0,上界为无穷大的边。(飞机可以空降到任何一点)

2.建汇t,所有出度为0的点向t连下界为0,上界为无穷大的边。(必须滑到没有出边的点才能停止)

3.对于原图中的每条边,连下界为1,上界为无穷大的边。(每条边至少经过一次)

这是一个有源汇有上下界最小流问题。运用解决这个问题的常用方法,修改建模:

1.修改上述建模中所有边为容量为无穷大。

2.对于上述建模,记边(u,v)的下界为b(u,v)。计算每个结点的度数为du(x) = \sum_{i} {b(i,x)} - \sum_{j} {b(x,j)}。建超级源s's'向所有du(x) > 0的结点连容量为du(x)的边;建超级汇t',所有du(x) \lt 0的结点向t'连容量为-du(x)的边。

3.在已建好的图上求s' - t'最大流。

4.ts连容量为无穷大的边。

5.在已建好的图上求s' - t'最大流。

最后ts连的边的流量就是网络最小流。可能上述建模稍微有点难理解,可以参考有上下界网络流