问题3055--选派选手3055: 选派选手
时间限制: 1 Sec 内存限制: 512 MB
提交: 0 解决: 0
[提交] [状态] [讨论版] [命题人:]题目描述
在银河系深处正要举行一场编程比赛，你的任务就是选出参赛选手。
有N个学生申请参加比赛，比赛共有M个项目，每个人都懂得一些各个项目的知识。我们把学生的知识水平用一些实数表示。你最多可以选出K名学生参赛，但没有一个人能同时参加几项比赛。一项比赛可以有多人参加。
给出每个学生的每项知识水平，从中选出参赛选手和他们所参加的项目，使知识水平之和最大。
输入
第1行包括3个整数N，M和K(1≤M≤100,1≤K≤N≤100)。
接下来的M行是每个人每个项目的知识水平。每一行有N个数对(i,s)，i表示学生编号，正实数s表示他们对应项目的知识水平。其中(0≤s≤10)，这N个数对是按知识水平的降序排列的。学生的编号从一到N。每一行中，每个学生的编号只会出现一次。
输出
仅一行，输出选出学生知识水平的最大值，保留一位小数。
样例输入
（1）
3 2 2
2 3.0 1 0.2 3 0.1
3 1.0 2 0.5 1 0.2
（2）
4 4 3
4 5.0 2 4.0 3 2.0 1 1.0
2 2.0 3 1.0 1 0.5 4 0.3
4 6.0 3 5.0 2 2.0 1 0.0
1 4.0 2 3.0 4 0.6 3 0.3
样例输出
（1）
4.0
有两个项目，第一个项目水平最高的学生是第二位，知识水平为3.0；其次是1号学生，知识水平为0.2，然后是知识水平为0.1的3号学生。
很明显，最优解是分别将2号和3号学生派去参加第一和第二个项目。
（2）
15.0
样例2说明：选3个人，选4号做3项目，3号做3项目，2号做1项目，一共得到15.0
来源/分类
[提交] [状态]