#P14485. [2025年广东省队集训]人员调度2

    ID: 13704 传统题 8000ms 1024MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3100二分图图论数据结构数学最短路拓扑排序网络流

[2025年广东省队集训]人员调度2

问题描述

两年以前,小 A 在省选 day1 场上遇到了 《人员调度》 此题,并精准识别出是 LOJ 黄金矿工的弱化版,可惜小 A 由于懒惰,没有去做该题,只能遗憾离场。

......

小 A 现在是一家公司的老板,该公司共有 nn 个员工,以及 nn 个岗位。第 ii 个员工的能力值为 aia_i,第 ii 个岗位的要求值为 bib_i,第 ii 个员工就职第 jj 个岗位对公司产生的基础收益为 ai+bj+(ai⊕bj)a_i+b_j+(a_i\oplus b_j)。其中 ⊕\oplus 表示二进制下的异或运算。

同时小 A 发现特定的员工就职特定的岗位会产生额外的效益。小 A 会给出 mm 条信息,每条信息形如 (x,y,w)(x,y,w),即第 xx 个员工就职第 yy 个岗位会产生 ww 的额外收益。

小 A 给出一个参数 KK,他想要知道,对于 1≤k≤K1\le k\le K,若 恰好有 kk 个员工进行就职,产生的总收益(基础收益+额外收益)最大和为多少?

输入格式

第一行三个整数 n,m,Kn,m,K,分别表示员工数/岗位数以及信息的条数,所给的参数。

第二行包含 nn 个整数,第 ii 个整数表示 aia_i。

第三行包含 nn 个整数,第 ii 个整数表示 bib_i。

接下来 mm 行每行包含 33 个整数 x,y,wx,y,w,含义如题所示。

输出格式

一行包含 KK 个整数,第 ii 个整数表示 k=ik=i 时的答案。

输入样例

5 0 5
1 2 3 4 5
1 2 3 4 5

输出样例

14 28 42 56 58

数据范围

对于 100%100\% 的数据,1≤n≤1051\leq n\le 10^5,0≤m≤5×1050\le m\le 5\times 10^5,1≤K≤min⁡(300,n)1\le K\le \min(300,n),0≤ai,bi<2120\le a_i,b_i< 2^{12},0≤w≤1050\le w\le 10^5。

保证不存在两条信息其 x,yx,y 完全相同。

测试点编号 nn mm KK
1∼21\sim 2 ≤50\leq 50 ≤2500\leq 2500 ≤10\leq 10
3∼43\sim 4 ≤300\leq 300 ≤104\leq 10^4 ≤300\leq 300
5∼75\sim 7 ≤105\leq 10^5 ≤5×105\leq 5\times 10^5 =1=1
8∼108\sim 10 ≤5\leq 5
11∼1311\sim 13 ≤5000\leq 5000 ≤105\leq 10^5 ≤20\leq 20
14∼1614\sim 16 ≤3×104\leq 3\times 10^4 ≤2×105\leq 2\times 10^5 ≤100\leq 100
17∼1817\sim 18 ≤5×104\leq 5\times 10^4 ≤3×105\leq 3\times 10^5 ≤200\leq 200
19∼2119\sim 21 ≤7×104\leq 7\times 10^4 ≤5×105\leq 5\times 10^5 ≤250\leq 250
22∼2522\sim 25 ≤105\leq 10^5 ≤300\leq 300