在线评测链接:P1191
题目内容
塔子哥老家有一座分层水库，这个水库按高度分为 N N N 层，从高到低编号分别为 0 , 1 , . . . , N − 1 0,1,...,N-1 0,1,...,N−1 。除最低层外每一层上都有一个蓄水池，通过若干管道将每一层面水池中的水输送至最低层的水库中，管道之间通过水控制阀连接(水控制阀总数为 M M M )，现要找到每一层中离水库最近的关键水控制阀。
某一层的关键水控制阀定义为从该层蓄水池流向水库的水要么经过该水控制阀且不全部流向更低层(不考虑水库层)关键水控制阀，或者不经过该水控制阀且必须经过更低层(不考虑水库层)的关键水控制阀。
即：第 n n n ( n < N − 2 n \lt N - 2 n<N−2 )层的关键水控制阀为 k n k_n kn ，从 n n n 层蓄水池流向水库的水如果流经 k n k_n kn ，则必须存在流经 k n k_n kn 的水未流经任何 k i k_i ki ( n < i ≤ N − 2 n\lt i\le N-2 n<i≤N−2 )，如未流经 k n k_n kn ，则至少流经一个 k i k_i ki ( n < i ≤ N − 2 n\lt i\le N-2 n<i≤N−2 )。 其中，第 N − 2 N-2 N−2 层的关键水控制阀为 k N − 2 k_{N -2} kN−2 ，必须使得所有从第 N − 2 N-2 N−2 层蓄水池流向水库的水全部经过 k N − 2 k_{N-2} kN−2
输入描述
第一行：输入两个整数 N N N 和 M M M ，其分别表示层数与水控制阀总数。
第二行：输入 M M M 个数字表示 I D ID ID 为 0 0 0 到 M − 1 M-1 M−1 的水控制阀所在层数，层数为递增顺序。
接下来输入 M M M 行，第 i i i 行中的第一个数字 k i k_i ki ，表示通过水控制阀 i − 1 i- 1 i−1 下一步可到达的水控制阀个数。该行后面的 k i k_i ki 个数字分别表示这些水控制阀的编号 I D ID ID ，若 k i k_i ki 为 0 0 0 则则表示下一步没有可到达的水控制阀。
注：最后一层有且只有一个水控制阀连接到水库，不同层中水只能由高层流向低层，同一层中水只能由小 I D ID ID 的水控制阀流向大 I D ID ID 的水控制阀。每层的最小 I D ID ID 的水控制阀只能接收来自该层蓄水池的水。
其中， 1 ≤ M ≤ 2000 1\le M\le 2000 1≤M≤2000 ， 1 ≤ N ≤ 2000 1\le N\le 2000 1≤N≤2000 ， 0 ≤ k i ≤ M 0\le k_i \le M 0≤ki≤M 。
输出描述
按从高到低输出每层(不包含水库层) 离水库最近(从该水控制阀到水库所经历的水控制阀数最少)的关键水控制阀编号，若该层不存在关键水控制阀，则该层输出 − 1 -1 −1 。
样例
样例1
输入
3 10
0 0 0 1 1 1 1 1 1 2
2 1 2
1 7
1 4
2 4 5
1 6
1 6
2 7 8
1 9
1 9
0
输出
1 6
样例解释
先考虑第 1 1 1 层，由于没有更低层，所以该层的关键水控制阀需要水池 1 1 1 中的流向水库的水全部流经该水控制阀，所以 3 3 3 和 6 6 6 符合条件，而水控制阀 6 6 6 离水库最近，故第 1 1 1 层结果为水控制阀 6 6 6 。
接着考虑第 0 0 0 层，若 2 2 2 为关键水控制阀，则流经水控制阀 1 1 1 的水并没有经过任何关键水控制阀，不符合条件。
水控制阀 1 1 1 和水控制阀 0 0 0 均符合关键水控制阀的定义，而水控制阀 1 1 1 离水库更近，所以离水库最近的关键水控制阀为水控制阀 1 1 1 。
所以最终结果为 1 6 。
样例2
输入
6 1 9
0 0 0 1 1 2 2 2 2 3 3 4 4 4 4 4 4 4 5
1 1
2 2 4
2 7 8
1 4
1 7
1 6
1 7
4 8 12 14 15
1 15
1 10
0
2 12 13
1 14
1 14
2 15 16
1 17
1 18
1 18
0
输出
2 -1 7 -1 14
样例解释
先考虑第 4 4 4 层，由于没有更低层，所以该层的关键水控制阀需要水池1中的流解释向水库的水全部流经该水控制阀，所以 11 11 11 和 14 14 14 符合条件，而水控制阀 14 14 14 离水库最近，故第 1 1 1 层结果为水控制阀 14 14 14 ；
接着考虑第 3 3 3 层，由于没有通向水库的水控制阀，故为 − 1 -1 −1 ；
接着考虑第 2 2 2 层，由于该层所有水流均流向水控制阀 7 7 7 ，而流经水控制阀 7 7 7 的水有流经更低层关键水控制阀 14 14 14 的也有流向非关键水控制阀 15 15 15 的故 7 7 7 为关键水控制阀， 5 , 6 5,6 5,6 水控制阀同理，但 7 7 7 离水库最近，故结果为水控制阀 7 7 7 ；
接着考虑第 1 1 1 层，第一层流经水控制阀 3 , 4 3,4 3,4 的水均流向了更低层的关键水控制阀 7 7 7 故该层无关键水控制阀，结果为 − 1 -1 −1 ；
最后考虑第 0 0 0 层，可以得到 2 2 2 为关键水控制阀，由于该层未流经水控制阀 2 2 2 的水均流向更低层的关键水控制阀 7 7 7 ，且流经 2 2 2 的水有未流经任何关键水控制阀到达水库的路线，故 2 2 2 为关键水控制阀。同样 0 0 0 ， 1 1 1 也为关键水控制阀，而 2 2 2 距离水库更近，故关键水控制阀为水控制阀 2 2 2 ；
综上，最终结果为 2 -1 7 -1 14 。
本文链接：https://my.lmcjl.com/post/4339.html
4 评论