#D. [2023csp-j模拟]羁绊

    传统题 文件IO:power 1000ms 256MiB

[2023csp-j模拟]羁绊

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述:

一个班级中有n个男生和m个女生,编号分别为1至n和1至m。这天学校组织运动会,老师需要选取其中p个男生和q个女生组成班级代表队参加运动会,在这些同学中,存在r种神奇的羁绊关系x y z,若编号为x的男生和编号为y的女生同时在代表队中,那么队伍中同学会表现地更好,队伍的实力会提升z,同一个人可以触发多个羁绊,请帮助老师选择同学组成最强的代表队,输出队伍实力最大可能的值

输入格式:

n m p q rn\ m\ p\ q\ r

x1 y1 z1x_1\ y_1\ z_1

x2 y2 z2x_2\ y_2\ z_2

...

xr yr zrx_r\ y_r\ z_r

输出格式:

一个整数表示队伍实力最大可能的值

样例:

3 4 2 3 7
1 1 9
1 2 7
1 3 15
1 4 6
2 2 3
2 4 6
3 3 6
37

考虑编号为1,2的男生和编号2,3,4的女生组成的代表队。

羁绊1不触发

羁绊2触发实力+7

羁绊3触发实力+15

羁绊4触发实力+6

羁绊5触发实力+3

羁绊6触发实力+6

羁绊7不触发

队伍实力的合计增加值7+15+6+3+6=37,是最大值。

4 5 3 2 9
2 3 5
3 1 4
2 2 2
4 1 9
3 5 3
3 3 8
1 4 5
1 5 7
2 4 8
26

提示

1<=n,m<=181<=n,m<=18

1<=p<=n,1<=q<=m1<=p<=n,1<=q<=m

1<=r<=nm1<=r<=n*m

模拟1

未参加
状态
已结束
规则
OI
题目
4
开始于
2023-9-23 14:00
结束于
2023-10-1 22:00
持续时间
200 小时
主持人
参赛人数
11