第一课堂
Current course
Participants
General
Topic 2
Topic 3
Topic 4
Topic 5
Topic 6
Topic 7
Topic 8
Topic 9
Topic 10
Topic 11
Topic 12
Topic 13
Topic 14
Topic 15
Topic 16
Topic 17
Topic 18
Topic 19
Topic 20
K- 联赛
Grade | 0 | Open Time | Thursday, 21 February 2013, 11:02 pm |
Discount | 0.8 | Time Discount | Thursday, 28 February 2013, 11:02 pm |
Allow late | Yes | Close Time | Thursday, 28 February 2013, 11:02 pm |
Input file | kleague.in | Output file | kleague.out |
【问题描述】
K- 联赛职业足球俱乐部的球迷们都是有组织的训练有素的啦啦队员,就像红魔啦啦队一样 (2002 年韩日世界杯上韩国队的啦啦队 ) 。这个赛季,经过很多场比赛以后,球迷们希望知道他们支持的球队是否还有机会赢得最后的联赛冠军。换句话说,球队是否可以通过某种特定的比赛结果最终取得最高的积分 ( 获胜场次最多 ) 。 ( 允许出现多支队并列第一的情况。 )
现在,给出每个队的胜负场数, w i 和 d j ,分别表示 team i 的胜场和负场 (1 ≤ i ≤ n) 。还给出 a i,j ,表示 team i 和 team j 之间还剩多少场比赛要进行 (1 ≤ i , j ≤ n) 。这里, n 表示参加联赛的队数,所有的队分别用 l , 2 ,…, n 来编号。你的任务是找出所有还有可能获得冠军的球队。
所有队参加的比赛数是相同的,并且为了简化问题,你可以认为不存在平局 ( 比赛结果只有胜或负两种 ) 。
【输入】
第一行一个整数 n (1 ≤ n ≤ 25) ,表示联赛中的队数。
第二行 2n 个数, w 1 , d 1 , w 2 , d 2 ,…, w n , d n ,所有的数都不超过 100 。
第三行 n^2 个数, a 1,1 , a 1,2 ,…, a 1,n , a 2,1 , a 2,2 , …, a 2,n ,…, a n,1 , a n,2 ,…, a n,m , 所有的数都不超过 10 。 a i,j =a j,i ,如果 i=j ,则 a i,j =0 。
【输出】
仅一行,输出所有可能获得冠军的球队,按其编号升序输出,中间用空格分隔。
【样例 1】
kleague.in
3
2 0 1 1 0 2
0 2 2 2 0 2 2 2 0
kleague.out
1 2 3
【样例 2】
kleague.in
3
4 0 2 2 0 4
0 1 1 1 0 1 1 1 0
kleague.out
1 2
【样例 3 】
kleague.in
4
0 3 3 1 1 3 3 0
0 0 0 2 0 0 1 0 0 1 0 0 2 0 0 0
kleague.out
2 4