1 solutions

  • 0
    @ 2026-9-18 18:33:17

    题目简述

    给定 n,mn,m,以及 mm 个形如 axi≥ayi+azi(1≤i≤m)a_{x_i}\ge a_{y_i}+a_{z_i}(1 \le i \le m) 的条件。问是否有一组正整数 (a1,a2,⋯ ,an)(a_1,a_2,\cdots,a_n) 满足所有条件,并且 a1+a2+⋯+an≤109a_1+a_2+\cdots+a_n \le 10^{9}。如果有,输出 a1+a2+⋯+ana_1+a_2+\cdots+a_n 的最小值;如果无解,输出 −1-1。

    算法1:暴力

    考虑连边 xi→yi,xi→zix_i\to y_i,x_i \to z_i. 注意到如果这个图里面有环,那么环上的最小值一定不满足对应的要求;如果图里面无环,找出拓扑序,按照拓扑序依次贪心确定每个数的最小可能值即可. 如果超过了 10910^9 直接退出就不会溢出. 时间复杂度 O(n+m)O(n+m).

    Information

    ID
    38
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    (None)
    Tags
    (None)
    # Submissions
    0
    Accepted
    0
    Uploaded By