Michael_Bryant最喜欢的G(al)G(ame)

那些悲伤,那些寂寞,那些几乎让自己放弃生活的希望的痛苦的回忆,绝对绝对不要将它们忘记。

Michael_Bryant最喜欢的番剧

抱歉⋯我已经绝对不可能再获得幸福了,因为⋯我发现⋯ 其实我⋯ 早就已经被幸福包围了

Michael_Bryant正在看的番剧

死亡一点也不温柔,只有无尽的黑暗和孤独。 就算联系得再紧密,人也是孤独的。

USACO 2002 FEB Chores家务

题目链接

这道题来自fzoj 所以不是hsannu的OIer们上不去
干脆不给链接了 直接把题粘下来吧

题目描述

农夫john有n(3<=n<=10,000)个家务要完成,每个家务需要的时间为time(1<=time<=100),但是有些家务需要在别的家务完成后才能开始,保证第k个家务能否开始,只与1..k-1中的某些家务有关。计算并输出完成n个家务活的最少时间。

输入

共n+1行,
第1行,1个整数n.
第2..n+1行,第i行,描述第i-1个家务的信息:需要的时间,前驱家务个数,前驱家务编号.

输出

1个整数,完成家务的最少时间.

样例输入

7
5 0
1 1 1
3 1 2
6 1 1
1 2 2 4
8 2 2 4
4 3 3 5 6

样例输出

23

提示

家务1开始时间0,结束时间5

家务2开始时间5,结束时间6

家务3开始时间6,结束时间9

家务4开始时间5,结束时间11

家务5开始时间11,结束时间12

家务6开始时间11,结束时间19

家务7开始时间19,结束时间为23

想说的话

这道题第一次做是大概四个月之前 当时一丁点思路都没有
现在再看 就舒服多了

题解

这题有大概三种思路
第一种是连图跑最长路
针对最长路神犇们都说只有spfa可以应对(我也不造为啥
这样的话我就干脆没试 既然只能用spfa肯定会被卡掉
事实证明确实这样23333...
第二种是我的做法
通过对数据的观察 我们发现家务顺序一定是从小到大
这样的话我们干脆直接从头到尾走一遍就好了
把每一个家务前驱最大值记下来
然后这个家务前驱跑完之后更新答案
这个做法有点捡漏的意思 但是数据确实就是这么给的
第三种是正解
Tarjan——拓扑排序
找入度为零的跑就行
具体实现我也不太会(我太弱了

附上题解二代码

写得这么通俗相信都能看懂

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注

隐藏