#CW32. 封锁通路(detour)
封锁通路(detour)
题目描述
小 W 正在检查一张由 个房间和 条单向通道组成的地图。地图是一张有向无环图,入口为房间 ,出口为房间 。第 个房间存放一件重量为 、价值为 的物品。
一条游览路线是从房间 到房间 的有向路径。小 W 会取得路径上所有房间的物品。只有物品总重量除以 的余数等于 时,这条路线才合法。
小 Z 会封锁一个房间。对每个 ,请分别计算房间 被封锁、路线不能经过该房间时:
- 合法路线能够取得的最大总价值;
- 达到最大总价值的不同路线数量,对 取模。
若不存在合法路线,输出 。
输入格式
第一行输入一个整数 ,表示测试数据组数。
每组数据中:
- 第一行输入两个整数 ;
- 接下来 行,第 行输入 ;
- 接下来 行,每行输入两个整数 ,表示一条从 到 的通道;
- 最后一行输入两个整数 。
输出格式
对每组数据输出 行。第 行表示房间 被封锁时的答案。
若不存在合法路线,输出 ;否则输出两个整数,依次表示最大总价值和达到该价值的路线数量。路线数量对 取模。
样例 1 输入
1
5 6
1 5
1 8
1 8
1 3
1 6
1 2
1 3
2 4
3 4
2 5
4 5
2 0
样例 1 输出
-1
22 1
22 1
-1
-1
样例 1 解释
未封锁时,经过房间 或经过房间 的两条路线均合法,价值均为 。封锁房间 后只能使用后一条,封锁房间 后只能使用前一条。入口、出口或房间 被封锁时不存在合法路线。
样例 2 输入
1
5 6
1 1
1 4
1 4
1 1
1 1
1 2
1 3
2 5
3 5
1 4
2 4
2 1
样例 2 输出
-1
6 1
6 1
6 2
-1
数据范围
对于所有测试数据:
- ;
- ,;
- ;
- ,;
- ;
- 图中没有重边,且图为有向无环图;
- 不保证原图存在从房间 到房间 的路径;
- 所有测试数据的 ,。
| 数据类别 | 分值 | 测试点 | 附加条件 |
|---|---|---|---|
| A | 10 | ,, | |
| B | 15 | ,, | |
| C | 20 | ||
| D | 25 | ,,,且每条通道均满足 | |
| E | 30 | 无额外限制 |