不知道答案是什么，做了一个，但是不知道对不对，大家只要说说算法是什么就行了！小弟求教了

描述

barty后宫三千，但是正宫只有一个。他的正宫为了他能好好学习，成为学霸，给他定下要求，一定要把和计算机相关的各种课程都学完。

 

对于每种课程，都会有几个或0个课程作为它的先修课程，只有把那些先修课程学完才能学习该课程，但是这个规定并不是特别严格。设barty的智商为T，且课程A有一门先修课程为B，根据B课程对A课程的影响，会规定一个相关系数C，如果T>＝C，就是说barty足够聪明，那么就可以无视先修课程B而直接去学习A，另外一个很关键的问题就是可能存在A是B的先修课程，B是C的先修课程，C又是A的先修课程（这在实际情况中也是可能存在的），但不会有课程是它自己的先修课。

 

需要你计算的就是：barty的智商最低为多少的时候可以让barty学完全部课程。

输入
输入的第一行是一个整数，为数据的组数t（t<=20）。

对于每组数据，第一行为2个正整数n和m（1<=n,m<=10000），分别表示课程数和课程先修关系数，之后的m行，每行三个数ai、bi、ci，表示bi为ai的一门先修课程，且相关系数为ci（1<=ai,bi<=n，ci<=109）。

输出
每组数据一行，为最低需要的智商。

样例输入
1
6 6
2 3 2
3 4 5
4 2 7
2 1 1
3 5 2
6 4 7
样例输出
2

好久没来了，大家新年好啊！

建立课程关系的有向图，依次从图中删去入度最大值最小的结点。
全部删完后，删除过程中删过的入度最大值即是那小子想完成学业所需的最低智商。

按你这个方法题目中的例子的结果还是2吗？看得不太懂啊

路过 赚积分

我的智商140，虽不是天才但做这个题还是有富余的，你可以在纸上画画图再质疑我。
今天只能拿手机上网，说起来不方便。

哈哈，不是质疑啦，我是删没有入度的节点，更改有向图的连接关系，再在剩余的回路中找最小系数，得到的就是结果；如果没剩回路，则需T值为0。但是感觉麻烦了，却想不到更好的办法。没太看懂你说的，有时间望详细解答哈！

没有入度相当于入度最大值为0。我所描述的算法是最容易构建的。不过耗时有点大，时间复杂度是O(m^2)。
你的问题是北航2068题。限时一秒，我试着提交了一下，结果超时。
直接从图入手找出最低关系值我想了很久也没有想到更快的方法。于是只能倒过来解决，判断某一智商值T是否可以解开图，然后用二分法逼近。
判断需要进行拓扑排序以确认是否存在回路，这一过程耗时O(n + m)，由于T的上限为一常数，所以二分法的耗时不在时间复杂度里考虑，所以总的时间复杂度也是O(n + m)。
按这一算法写的代码提交AC，耗时156毫秒。

赚点分分

不好意思啊，分不多，不散了啊