#2046. 春游

    ID: 2046 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>其他构造贪心搜索枚举近似算法区间 DP树的重心状态压缩背包 DP

春游

说明

小 C 管理着一个很大的动物园,这个动物园有许许多多奇奇怪怪的小动物。不过他们都有一个共同的特点,就是非常喜欢春天。于是,为了提高动物园的和谐程度,小 C 决定带小动物们出去春游。

不过,春游是一件非常麻烦的事情。每个小动物都会带来一定的麻烦程度;更麻烦的是,特定的小动物待在一起会有特殊的麻烦程度变化。比如,跳蚤国王和蛐蛐国王待在一起,事情就麻烦了,因为蛐蛐国王总是想把跳蚤国王的子民们分割开来;而花鸡和青蛙待在一起,却可以使气氛更加的活跃,因为他们经常在一起讨论关于眼镜的保养问题,谈笑风生间时间很快就过去了,自然管理起来就不那么麻烦。

由于小动物实在是太多了,小 C 决定分批次带小动物们出去春游。为了方便管理,每次春游时小 C 会选出 MM 个队长,来管理这次参与春游的其他 NN 位小动物。其中,第 ii 位队长的麻烦程度是 bib_i,第 ii 个小动物的麻烦程度是 aia_i。队长以身作则,答应了小 C 他们和其他小动物的麻烦程度不会发生特殊变化;所以所有的变化都是在 NN 位小动物之间发生的。经过小 C 调查,一共有 KK 对小动物存在着能够导致变化的友谊/矛盾,形式化地讲有两种:

  1. uiu_iviv_i 在一个小队时,这个小队的麻烦程度会增加 wiw_i

  2. uiu_iviv_i 在一个小队时,这个小队的麻烦程度会乘以 wiw_i

当方案确定后,所有 1 类型的变化先生效,然后所有 2 类型的变化依次生效。(也就是说,1 类型变化增加的值同样会被 2 类型变化乘上系数,并且系数是连乘起来的)

形式化地说,对于一个小队 S={B,A1,A2,...,Ak}S=\{B,A_1,A_2,...,A_k\}(其中队长是 BB),SS 的麻烦程度为 $\prod_{u_{2,i}\in S,v_{2,i}\in S} w_{2,i}(b_B+\sum_{i=1}^k a_{A_i}+\sum_{u_{1,i}\in S,v_{1,i}\in S} w_{1,i})$(其中下标 (1,i)(1,i) 表示第一种变化的第 ii 个,下标 (2,i)(2,i) 表示第二种变化的第 ii 个)。

现在小 C 想分 10 次带小动物们出去春游,她想最小化每次春游麻烦程度最大的小队的麻烦程度。她找到了你来帮他解决这个问题,你能给她尽量优秀的方案么?

输入格式

本题为提交答案题。所有输入数据 spring1.in ~ spring10.in 见附加文件下载,分别对应 10 次春游的情况,选手文件见题目描述上方附加文件

对于每组输入数据:

第一行是三个空格隔开的正整数,分别是 N,M,KN,M,K,即待分配队员数,小队数,以及特殊变化数。

第二行是 NN 个非负整数,第 ii 个数表示 aia_i,即待分配的第 ii 位队员的麻烦程度。

第三行是 MM 个非负整数,第 ii 个数表示 bib_i,即第 ii 位队长的麻烦程度。

第四行起共 KK 行,每行格式为以下两种中的一种:

  1. 1 ui vi wi1\ u_i\ v_i\ w_i 表示一种加的特殊变化;

  2. 2 ui vi wi2\ u_i\ v_i\ w_i 表示一种乘的特殊变化。

其中有1ui<viN1 \leq u_i \lt v_i \leq N

输出格式

输出文件为 spring1.out ~ spring10.out,分别对应相应的输入文件。

对于每个输出文件,请输出 2M2M 行:

2i12i - 1 行,请输出一个非负整数 cic_i,表示你的方案里,有 cic_i 个小动物被分配到了第 ii 个小队;

2i2i 行,请输出 cic_i 个正整数 di,jd_{i, j},第 jj 个表示分配到这个队伍的小动物标号 di,jd_{i, j}。如果 ci=0c_i = 0,请输出一个空行。

你可以认为,你的答案如果能被下发的 checker 接受,那么就能够被评测程序接受。

你可以在你的输出文件的第 2M+12M + 1 行后输出任意额外的内容;如果你有兴趣的话,我们希望你能把你的解法写在答案后面。

样例

4 2 4
2 4 8 16
9 10
1 1 2 2
1 1 3 -4
2 2 3 1.5
2 2 4 0.5
2
1 3
2
2 4

如果第 44 组条件不生效,那么不含队长时答案将一定不会低于 1616

如果第 44 组条件生效,此时若第33组条件生效,那么不含队长时答案一定不会低于 (4+8+16)×1.5×0.5=21(4 + 8 + 16) \times 1.5 \times 0.5 = 21

如果第 44 组条件生效,第33组条件不生效,那么剩余情况有:

  1. {{3},{1,2,4}}: \{\{3\}, \{1, 2, 4\}\}:\ 最优方案为 $\mathrm{max}(8 + 9, (2 + 4 + 16 + 2 + 10) \times 0.5) = 17$

  2. {{1,3},{2,4}}: \{\{1, 3\}, \{2, 4\}\}:\ 最优方案为 $\mathrm{max}(2 + 8 - 4 + 9, (4 + 16 + 10) \times 0.5) = 15$

可以证明,对于样例的最优分配方案答案即为 15 15 ,且最优方案是唯一的。

数据范围

输入数据已经给出。以下是对于所有输入数据,均满足的限制:

$2 \leq N, M \leq 5000, 0 \leq K \leq 5000, 0 \leq a_i \leq 10 ^ 4, 0 \leq b_i \leq 10 ^ 6;$

对于操作 11,有 wi104|w_i| \leq 10 ^ 4,且此时 wiw_i 为整数;

对于操作 22,有 0.5wi20.5 \leq w_i \leq 2,且最多有一位小数;

对于一对 (ui,vi)(u_i, v_i) 最多只有一个限制;

对于任意分配方案,所有小队的麻烦程度均不小于 11。请注意,可能存在一些情况使得某些小队麻烦程度会非常大,可能会带来不必要的精度误差,请谨慎处理;

最优答案满足 1ans2301 \leq \mathrm{ans} \leq 2 ^ {30}

评测方式

我们有十个评分文件 spring1.ans~spring10.ans,分别对应每个测试点作为评分标准;每个评分文件共 1111 行,第 ii 行一个评分参数 wiw_i,具体意义将在下面给出。

本题中,每个测试点单独进行评分,每个测试点 1010 分。

如果选手的输出格式不合法,则得 00 分。

如果你的输出不满足以下条件,得 00 分:

  1. i=1Nci=N\sum_{i=1}^N c_i = N,且对于所有 cic_i0ciN0 \leq c_i \leq N

  2. 所有 NN 个小动物均各自被分配到 MM 个小队中的一个,且仅被分配一次。

否则,我们认为你的方案正确,并按照以下规则得分。

对于每个测试点,我们设置了 1111 个评分参数 w0,w1,w2,,w9,w10w_0,w_1,w_2,…,w_9,w_{10},有 wi<wi+1w_i \lt w_{i + 1}

如果你的答案大于 w0w_0,那么你这个测试点得 00 分;

如果你的答案不大于 w10w_{10},那么你可以得到 1010 分;

否则,我们设你的答案为 xx,设 ii 满足 wi+1x<wiw_{i + 1} \leq x \lt w_i,那么对于该测试点你可以得到 $i + 1 - \frac {\mathrm{out} - w_{i + 1}} {w_i - w_{i + 1}}$ 分,按四舍五入保留一位小数;也就是说,9.95 分及以上的提交均算作 10.0 分。

你该题的得分是所有测试点得分加和后四舍五入;也就是说,99.5 分以上的提交均算作 100 分。

下发文件

选手文件见题目描述上方附加文件

在附加文件里,有 spring1.out~spring10.out。

同时,我们提供了 spring0.in,spring0.out,spring0.ans,对应样例在附加文件中。

同时,我们提供了一个 checker,来对你的输出进行检验。你可以在命令行运行:./checker #,这样 checker 会读取当前目录下的spring#.in 和 spring#.out 来评测你的方案的价值;如果目录下同时有 spring#.ans,那么 checker 会同时给出你的得分。

请注意,checker 不会检查输入文件正确性;如果你想测试非下发测试点,请注意输入文件的正确性,并满足约定与限制,否则检验结果可能不准确。

来源

loj.ac