OI题库

【问题描述】

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