# 拓扑排序

Acwing456 车站分级

原题链接:Acwing456

题目描述:一条单向的铁路线上,依次有编号为 1, 2, …, n 的 n 个火车站。

每个火车站都有一个级别,最低为 1 级。

现有若干趟车次在这条线路上行驶,每一趟都满足如下要求:如果这趟车次停靠了火车站 x,则始发站、终点站之间所有级别大于等于火车站 x 的都必须停靠。(注意:起始站和终点站自然也算作事先已知需要停靠的站点) 

例如,下表是 5 趟车次的运行情况。

其中,前 4 趟车次均满足要求,而第 5 趟车次由于停靠了 3 号火车站(2 级)却未停靠途经的 6 号火车站(亦为 2 级)而不满足要求。

1163900-20170818013814084-1540659827.jpg

现有 m 趟车次的运行情况(全部满足要求),试推算这 n 个火车站至少分为几个不同的级别。

……

READ MORE

Acwing1192 奖金

原题链接:Acwing1192

题目描述:由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出,Yali Company总经理Mr.Z心情好,决定给每位员工发奖金。

公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少。

于是Mr.Z下令召开 m 方会谈。

每位参加会谈的代表提出了自己的意见:“我认为员工 a 的奖金应该比 b 高!”

Mr.Z决定要找出一种奖金方案,满足各位代表的意见,且同时使得总奖金数最少。

每位员工奖金最少为100元,且必须是整数。

……

READ MORE