luogu#P3921. 小学数学题

    ID: 7949 远端评测题 1500ms 500MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>动态规划dp洛谷原创O2优化广度优先搜索BFS期望

小学数学题

题目背景

露米娅:我来先考你一道小学数学题吧!

琪露诺:好!小学的题我肯定都会!

题目描述

露米娅:有 n n 只妖精要跨过雾之湖,由于湖边大雾弥漫,妖精们看不清湖到底有多大,不想从边上绕过去。

湖上有一条船个传送器,且这个传送器每次只能载 r r 只妖精跨过湖面(注意传送器可以同时把两侧的妖精分别运到对岸,但每次运送的总妖精数不能超过 r r )。

这些妖精还很喜欢搞事,所以在任何时刻,都需要满足一些条件,其中第一种条件有 m1 m_1 个,第二种条件有 m2 m_2 个。

第一种条件形如 妖精 a a 和妖精 b b 必须要在湖的同一侧;

第二种条件形如 当妖精 a a 在湖的一侧时,妖精 b b 和妖精 c c 不能同时在湖的另一侧。

现在给出这些条件,求:

  1. 至少需要传送器几次才能让所有妖精到湖的对岸

  2. 在保证次数最少的前提下,求过河方案数

输入格式

第一行四个整数 n,m1,m2,r n , m_1 , m_2 , r

接下来 m1 m_1 行每行2个整数 a,b a , b ,代表第一种条件

接下来 m2 m_2 行每行3个整数 a,b,c a , b , c , 代表第二种条件

输出格式

两个整数,分别为最少使用传送器次数和方案数,用空格分隔

若无法全部过河,输出"-1 0"(不含引号)

1 0 0 1

1 1

5 0 0 2

3 90

3 1 0 1
1 2

-1 0

提示

对于 30% 30 \% 的数据, n10 n \leq 10

对于另外 10% 10 \% 的数据, m1=m2=0 m_1 = m_2 = 0

对于 100% 100 \% 的数据, a,b,cn15 a,b,c \leq n \leq 15 m1,m250 m_1 , m_2 \leq 50 r109 r \leq 10^9

请不要相信洛谷评测机的速度,如果得了80分以上,可以等人少的时候再交一次。但如果得了60分以下,说明可能写的不是正解,就不要再虐萌萌哒评测机啦