Problem1035--#2029. 「SHOI2016」巧克力

1035: #2029. 「SHOI2016」巧克力

Time Limit: 1 Sec  Memory Limit: 256 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

D 神给他的妹子买了好多好多的巧克力,放在他的储藏室中。作为爱吃巧克力的小 R,当然要去 D 神的储藏室中偷吃巧克力了。

D 神的储藏室中共有 nnn 个巧克力储藏点,编号从 000n1,每个储藏点中有一块巧克力。共有 mmm 条单向道路,每条单向路径连接了两个储藏点。小 R 从编号为 000 的储藏点出发,由于他太爱吃巧克力了,他只要经过一个储藏点就一定会吃掉那块巧克力。另外,他不能经过同一个储藏点两次,否则就会触发警报惊动 D 神。

每块巧克力的甜度不同,小 R 吃的第 iii 块巧克力可以感受到 ski1 的甜度,其中 sss 是该巧克力本身的甜度,kkk 是给定的不大于 111 的正实数。小 R 感受到的总甜度是他吃每一块巧克力感受到的甜度之和。请给出一条路线使得小 R 感受到的总甜度尽量大。

输入格式

输入文件为 chocolate1.in ~ chocolate10.in

第一行包含两个正整数 n,mn, mn,m 和一个正实数 k (0≤k≤1)k\ (0 \leq k \leq 1)k (0k1)nnn 表示巧克力储藏点的数量,mmm 表示单向道路的数量,kkk 表示甜度的衰减系数。

第二行 nnn 个正整数,分别表示每块巧克力的甜度。

接下来 mmm 行,每行两个正整数 u,vu, vu,v,表示有一条从 uuuvvv 的单向边。

输出格式

你需要提交输出文件 chocolate1.out ~ chocolate10.out

第一行一个非负整数 lll,表示路径长度。
第二行 lll 个正整数,依次表示经过每一个储藏点的标号。

样例

样例输入

5 5 0.5
1 3 5 7 2
0 1
0 2
1 3
3 1
2 3
3 4

样例输出

4
0 2 3 1

样例解释

这条路线的总收益为 1+0.5×5+0.25×7+0.125×3=5.6251 + 0.5 \times 5 + 0.25 \times 7 + 0.125 \times 3 = 5.6251+0.5×5+0.25×7+0.125×3=5.625
另一条路线为 0 2 3 40 \ 2 \ 3 \ 40 2 3 4,总收益为 1+0.5×5+0.25×7+0.125×2=5.51 + 0.5 \times 5 + 0.25 \times 7 + 0.125 \times 2 = 5.51+0.5×5+0.25×7+0.125×2=5.5

数据范围与提示

评分方式

对于每个测试点,如果你输出的路线出现了以下问题,则该测试点得 000 分:

  • 含有非法字符;
  • 路线不以编号为 000 的点开始;
  • 任意的相邻两个点之间不存在道路;
  • 某一个点经过超过一次;
  • 经过了不存在的点。

否则,对于每个测试点,假设你的路线能获得的总收益是 ans\mathrm{ans}ans,我们从小到大给出了 101010 个评分参数 s1,s2,,s10。如果 ans≥s10\mathrm{ans} \geq s_{10}anss10,你将获得 101010 分。否则,如果 si≤ans<si+1s_i \leq \mathrm{ans} < s_{i + 1}sians<si+1,你将获得 iii 分。

Source/Category