Information
- ID
- 38
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- (None)
- Tags
- (None)
- # Submissions
- 0
- Accepted
- 0
- Uploaded By
给定 n,m,以及 m 个形如 axi≥ayi+azi(1≤i≤m) 的条件。问是否有一组正整数 (a1,a2,⋯,an) 满足所有条件,并且 a1+a2+⋯+an≤109。如果有,输出 a1+a2+⋯+an 的最小值;如果无解,输出 −1。
考虑连边 xi→yi,xi→zi. 注意到如果这个图里面有环,那么环上的最小值一定不满足对应的要求;如果图里面无环,找出拓扑序,按照拓扑序依次贪心确定每个数的最小可能值即可. 如果超过了 109 直接退出就不会溢出. 时间复杂度 O(n+m).
By signing up a Hydro universal account, you can submit code and join discussions in all online judging services provided by us.