QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100
Statistics

题目描述

对于任意一张 DAG $G=(V,E)$ 和图中的一个起始点 $s_1\in V$,倍增小游戏的规则为:

  • 在第 $i$ 轮操作($i=1,2,\cdots$)中,玩家选取一条起点为 $s_i$ 的非空路径 $p_i$,使得所有属于这条路径的边的边权和恰为 $(i+1)$ 的倍数。如果无法选择出满足倍数要求的路径,则称游戏失败,玩家将不会获得任何分数;否则,本轮操作成功,并记 $p_i$ 的终点为 $s_{i+1}$。

  • 在第 $i$ 轮操作成功后,玩家可以选择结束游戏或者继续第 $(i+1)$ 轮操作。如果选择结束游戏,则称选择出的 $i$ 条路径 $p_1, \cdots, p_i$ 为倍增路径,并计算得分。

如果游戏没有失败,则在结束游戏时,对于选出的倍增路径 $p_1, \cdots, p_k$,定义游戏的分数为 $\sum_{i=1}^k a_i \left|p_i\right|/k$,其中 $|p_i|$ 表示路径 $p_i$ 包含的边数,$a_i$ 是输入给定的权值。显然,无论如何选取路径,最多也只能选出 $(n-1)$ 条路径,因此输入中只给出了 $a_1, \cdots, a_{n-1}$。

为了设置每张图的通关要求,请对给出的 DAG 和起始点,计算该游戏的最大分数。

输入格式

输入的第一行包含三个由空格隔开的正整数 $n$,$m$,$s_1$,表示给出的图中点的数量、边的数量及起始点的编号。保证 $2\le n \le 100$,$1\le m\le \frac{n(n-1)}{2}$,$1\le s_1\le n$。

输入的第二行包含 $(n-1)$ 个由空格隔开的正整数 $a_1, \cdots, a_{n-1}$,表示计算分数时的权重。保证 $1\le a_1\le a_2\le\cdots\le a_{n-1}\le 10^9$。

接下来 $m$ 行,每行输入三个由空格隔开的正整数 $u_i, v_i, w_i$,描述图中一条由 $u_i$ 连向 $v_i$,权值为 $w_i$ 的单向边。保证 $1\le u_i, v_i\le n$,$u_i\ne v_i$,$1\le w_i\le 10^9$,图是连通的且没有重边。

输出格式

输出仅一行,包括两个整数,由空格隔开。

如果可以选出至少一条路径,则存在一种最优的选取方案使得分数最大,记这个最优分数的最简分数表示为 $p/q$(当最优分数恰为整数时认为 $q=1$),则输出 $p$,$q$。否则,如果无论如何选取都无法选取出至少一条路径,则输出 -1 -1

样例数据

样例 1 输入

5 5 1
1 11 21 1211
1 2 4
1 3 11
2 5 9
3 4 12
4 5 13

样例 1 输出

6 1

样例 1 解释

选出的倍增路径为 $p_1 = ((1, 2)), p_2 = ((2, 5))$。

样例 2 输入

9 16 1
1 10 100 1000 10000 100000 1000000 10000000
1 2 2
1 3 3
2 3 5
2 5 7
3 4 11
3 5 13
3 6 17
3 7 19
4 7 23
5 6 29
5 8 31
6 7 37
6 8 41
6 9 43
7 9 47
8 9 53

样例 2 输出

221 3

子任务

对于 $100\%$ 的数据,保证 $2\le n\le 100$,$1\le m\le \frac{n(n-1)}{2}$,$1\le s_1, u_i, v_i\le n$,$1\le a_1 \le \cdots\le a_{n-1}\le 10^9$,$1\le w_i\le 10^9$,输入的图是连通的且没有重边。