2017-2018年问题求解(三)期末上机考试 Day2 题解

C. 花椰菜与西兰花

题意:有一块菜地,被分成 $latex n \times m$ 格,每格被种上花椰菜、西兰花或什么都不种。现在要在格子之间建一些篱笆,使得被篱笆分隔出来的每一连通区域中,至多只有一种作物。问篱笆的总长度最少是多少。

数据范围:$latex 1 \leq n \leq 50, 1 \leq m \leq 1000$

题解:最小割还是挺明显的。源点到所有花椰菜连上无穷容量边,所有西兰花到汇点连无穷容量边,然后相邻两个区域连容量为 1 的双向边。根据 MFMC 定理,答案就是从源点到汇点的最大流。

D. 旅游路线

题意:有 $latex n$ 个区域,每个区域内有 $latex s_i$ 个车站。区域内的车站之间移动需花费 $latex k_i$ 时间;此外,还有 $latex m$ 辆班车来回于两个车站之间,并需要花费 $latex c_j$ 代价。问从 1 号区域的第 1 个车站到 $latex n$ 号区域至少需要花费多少时间。

数据范围:

  • 部分数据满足 $latex 1≤n≤20, 1≤m≤100, 1≤s_i≤5, 1≤k_i, c≤1000$;
  • 部分数据满足 $latex 1≤n≤1000, 1≤m≤50000, 1≤s_i≤200, 1≤k_i, c≤1000$;
  • 部分数据满足 $latex 1≤n≤30000, 1≤m≤2*10^5, s_i=1, 1≤k_i, c≤1000$;
  • 部分数据满足 $latex 1≤n≤5000, 1≤m≤2*10^5, 1≤s_i≤50, 1≤k_i, c≤1000$。

题解:最短路,但是裸的 Dijkstra 肯定是过不了的。这是因为区域内暴力连边的话,会形成完全图,导致边数爆炸。为此,可以为每个区域设置一个特殊节点,该节点可以表示从区域内任何一个节点出发。这样,每个区域内的点都可以连一条长度为 $latex k_i$ 的单向边到该特殊节点,此外,从该区域中的某一点出发的边,同样也可以从特殊节点出发。这样整个图中只有 $latex m + \sum s_i $ 条边,跑 Dijkstra 就不会T了。

发表评论

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