当前位置:首页 > 图论 > 最短路径 > 正文
洛谷P7916交通规划(CSP2021)
108+

题目大意:已知一个n*m网格每条边的费用,现在要求给定点染色,如果相邻两点颜色不同,需要付出边权的费用,有些点颜色已确定,其他点染成黑白颜色,最小费用是多少?(55分代码)

题目描述

给定一个平面上 $n$ 条水平直线和 $m$ 条垂直直线,它们相交形成 $n$ 行 $m$ 列的网格,从上到下第 $r$ 条水平直线和从左到右第 $c$ 条垂直直线之间的交点称为格点 $(r, c)$。网格中任意两个水平或垂直相邻的格点之间的线段称为一条边,每条边有一个非负整数边权。

进行 $T$ 次询问,每次询问形式如下:

给出 $k$($T$ 次询问的 $k$ 可能不同)个附加点,每个附加点位于一条从网格边缘向外出发的射线上。所有从网格边缘向外出发的射线按左上-右上-右下-左下-左上的顺序依次编号为 $1$ 到 $2 n + 2 m$,如下图:

对于每次询问,不同附加点所在的射线互不相同。每个附加点和最近的格点之间的线段也称为一条边,也有非负整数边权(注意,在角上的格点有可能和两个附加点同时相连)。

给定每个附加点的颜色(黑色或者白色),请你将网格内每个格点的颜色染成黑白二者之一,并使得所有两端颜色不同的边的边权和最小。请输出这个最小的边权和。

输入输出格式

输入格式

第一行,三个正整数 $n, m, T$,分别表示水平、垂直直线的数量,以及询问次数。

接下来 $n – 1$ 行,每行 $m$ 个非负整数。其中第 $i$ 行的第 $j$ 个非负整数 ${x 1}_{i, j}$ 表示 $(i, j)$ 和 $(i + 1, j)$ 间的边权。

接下来 $n$ 行,每行 $m – 1$ 个非负整数。其中第 $i$ 行的第 $j$ 个非负整数 ${x 2}_{i, j}$ 表示 $(i, j)$ 和 $(i, j + 1)$ 间的边权。

接下来依次输入 $T$ 组询问。第 $i$ 组询问开头为一行一个正整数 $k_i$ 表示这次询问附加点的总数。接下来 $k_i$ 行每行三个非负整数。其中第 $j$ 行依次为 ${x 3}_{i, j}, p_{i, j}, t_{i, j}$ 表示第 $j$ 个附加点和相邻格点之间的边权、所在的射线编号以及附加点颜色($0$ 为白色,$1$ 为黑色)。保证同一组询问内 $p_{i, j}$ 互不相同。

每行的多个整数由空格分隔。

输出格式

输出 $T$ 行,第 $i$ 行输出一个非负整数,表示第 $i$ 次询问染色之后两端颜色不同的边权和的最小值。

输入输出样例

输入样例 #1

2 3 1
9 4 7
3 8
10 5
2
19 3 1
17 9 0

输出样例 #1

12

输入样例 #2

见附件中的 traffic/traffic2.in

输出样例 #2

见附件中的 traffic/traffic2.ans

输入样例 #3

见附件中的 traffic/traffic3.in

输出样例 #3

见附件中的 traffic/traffic3.ans

输入样例 #4

见附件中的 traffic/traffic4.in

输出样例 #4

见附件中的 traffic/traffic4.ans

输入样例 #5

见附件中的 traffic/traffic5.in

输出样例 #5

见附件中的 traffic/traffic5.ans

说明

**【样例解释 #1】**

最优方案:$(1, 3), (1, 2), (2, 3)$ 为黑色;$(1, 1), (2, 1), (2, 2)$ 为白色。

**【数据范围】**

| 测试点编号 | $n, m \le$ | $k_i \le$ |
|:-:|:-:|:-:|
| $1 \sim 2$ | $5$ | $50$ |
| $3 \sim 5$ | $18$ | $2$ |
| $6 \sim 8$ | $18$ | $50$ |
| $9 \sim 10$ | $100$ | $2$ |
| $11 \sim 12$ | $100$ | $50$ |
| $13 \sim 16$ | $500$ | $2$ |
| $17 \sim 20$ | $500$ | $50$ |

对于所有数据,$2 \le n, m \le 500$,$1 \le T \le 50$,$1 \le k_i \le \min \{ 2 (n + m), 50 \}$,$1 \le \sum_{i = 1}^{T} k_i \le 50$,$0 \le x \le {10}^6$,$1 \le p \le 2 (n + m)$,$t \in \{ 0, 1 \}$。

保证对于每个 $i \in [1, T]$,$p_{i, j}$ 互不相同。

解题思路

暴力:从上往下、从左往右,暴力枚举每个点染成的颜色,最后计算费用,因为n、m最大值是5,点最多有25个,时间复杂度是$O(2^{n*m})$,不剪枝会超时。我们可以一边染色,一般计算费用:每确定一个点的颜色,跟左边和上边比较,颜色不同累加边权,遇到右边界、下边界,多加一下即可,这样可得10分;记录最后m个点是颜色状态,加入记忆化剪枝,可得25。(改倒搜即轮廓线DP,常数太大得分不高。)

对偶图、最小割:如果只有两个点、两种不同的颜色,实际上就是找出一些边,将这两个点分割开来。我们可以把每个网格(区域)看成一个点,网格看成边,从特殊点的一边格子网另一边格子跑最短路,即可得到这个最小割,两部分加起来可得55分。

程序实现

洛谷P7916交通规划(CSP2021):等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter