题目描述(ID:12047)
标题: 引爆炸弹(SPFA)
标签:
详情: 有n个炸弹,有些炸弹牵了一根单向引线(也就是说引线只有在这一端能被炸弹点燃),只要引爆了这个炸弹,用引线连接的下一个炸弹也会爆炸。每个炸弹还有个得分,当这个炸弹被引爆后就能得到相应得分。
现在要你引爆k个炸弹,使得分最大。
输入格式:
第1行两个整数n、k。
接下来n行每行两个整数a[i]、b[i]。a[i]表示这个炸弹用引线连接的下一个炸弹,如果a[i]为0,则表示这个炸弹没连接引线。b[i]表示这个炸弹的得分。
输出格式:
仅一个数,表示最大得分。
限制: 1≤b[i]≤1000000
对于30%的数据,n≤1000 k≤30
对于60%的数据,n≤50000 k≤100
对于100%的数据,n≤200000 k≤500
样例:

输入

8 2
0 1
1 1
2 100
2 100
0 1
5 1
6 2
6 2

输出

202
登录并解答