#yXTTJlydlt60x6701. 银河

银河

好的，这是整理好的题面，不含解题思路，只包含样例解释。

题目描述

银河中的恒星浩如烟海，我们只关注那些最亮的恒星。
我们用一个正整数表示恒星的亮度，数值越大则恒星越亮，恒星的亮度最暗是 1。

现在对于 NN 颗我们关注的恒星，有 MM 对亮度之间的相对关系已经判明。
你的任务是求出这 NN 颗恒星的亮度值总和至少有多大。

如果无解（即存在矛盾的关系），输出 −1-1。

输入格式

第一行两个整数 NN 和 MM。
之后 MM 行，每行三个整数 T,A,BT, A, B，表示一对恒星 AA 和 BB 之间的亮度关系。恒星的编号从 1 开始。

  • 如果 T=1T=1，说明 AA 和 BB 亮度相等。
  • 如果 T=2T=2，说明 AA 的亮度小于 BB 的亮度。
  • 如果 T=3T=3，说明 AA 的亮度不小于 BB 的亮度（即 A≥BA \ge B）。
  • 如果 T=4T=4，说明 AA 的亮度大于 BB 的亮度。
  • 如果 T=5T=5，说明 AA 的亮度不大于 BB 的亮度（即 A≤BA \le B）。

输出格式

输出一个整数，表示 NN 颗恒星亮度总和的最小可能值。
若无解，输出 −1-1。

数据范围

  • N≤100000N \le 100000
  • M≤100000M \le 100000

输入样例

5 7 
1 1 2 
2 3 2 
4 4 1 
3 4 5 
5 4 5 
2 3 5 
4 5 1

输出样例

11

样例解释

N=5N=5，M=7M=7，关系如下（亮度均为正整数，最小为 1）：

  1. T=1,A=1,B=2T=1, A=1, B=2：亮度 1=21 = 2
  2. T=2,A=3,B=2T=2, A=3, B=2：亮度 3<23 < 2 → 即 3≤2−13 \le 2 - 1（注意亮度是整数，A<BA<B 可化为 A≤B−1A \le B-1）
  3. T=4,A=4,B=1T=4, A=4, B=1：亮度 4>14 > 1 → 4≥1+14 \ge 1 + 1 即 4≥24 \ge 2（或 4≤14 \le 1 不成立，应表达为 4≥1+14 \ge 1+1）
    更准确：A>BA > B 化为 A≥B+1A \ge B + 1。
  4. T=3,A=4,B=5T=3, A=4, B=5：亮度 4≥54 \ge 5 → 即 4≥54 \ge 5（显然不可能，但先记录下来）
  5. T=5,A=4,B=5T=5, A=4, B=5：亮度 4≤54 \le 5 → 4≤54 \le 5（与上一条矛盾）
  6. T=2,A=3,B=5T=2, A=3, B=5：亮度 3<53 < 5 → 3≤43 \le 4
  7. T=4,A=5,B=1T=4, A=5, B=1：亮度 5>15 > 1 → 5≥25 \ge 2

尝试构造最小亮度

把不等式标准化为 xA≤xB+cx_A \le x_B + c 的形式，并检查矛盾。

  1. 1=21 = 2 → x1≤x2x_1 \le x_2 且 x2≤x1x_2 \le x_1
  2. 3<23 < 2 → x3≤x2−1x_3 \le x_2 - 1
  3. 4>14 > 1 → x4≥x1+1x_4 \ge x_1 + 1
  4. 4≥54 \ge 5 → x4≥x5x_4 \ge x_5
  5. 4≤54 \le 5 → x4≤x5x_4 \le x_5
    由 4 和 5 得 x4=x5x_4 = x_5
  6. 3<53 < 5 → x3≤x5−1x_3 \le x_5 - 1
  7. 5>15 > 1 → x5≥x1+1x_5 \ge x_1 + 1

还有 xi≥1x_i \ge 1。

由 1：x1=x2x_1 = x_2
由 5 和 4：x4=x5x_4 = x_5
由 7 和 x4=x5x_4 = x_5 得 x4≥x1+1x_4 \ge x_1 + 1，这和 3 一致（x4≥x1+1x_4 \ge x_1 + 1 重复）。
由 2：x3≤x2−1=x1−1x_3 \le x_2 - 1 = x_1 - 1
由 6：x3≤x5−1=x4−1x_3 \le x_5 - 1 = x_4 - 1

为让总和最小，取 x1=1x_1=1，则 x2=1x_2=1，x3≤0x_3 \le 0，但亮度最小为 1，矛盾吗？
x3≤x1−1=0x_3 \le x_1 - 1 = 0，但 x3≥1x_3 \ge 1，不可能同时满足。所以无解？

但样例输出是 11，说明有解。我推导可能出错。

重新仔细看第 2 条：T=2,A=3,B=2T=2, A=3, B=2 表示 3<23 < 2，即 x3<x2x_3 < x_2，所以 x3≤x2−1x_3 \le x_2 - 1。
第 6 条：T=2,A=3,B=5T=2, A=3, B=5 表示 x3<x5x_3 < x_5，即 x3≤x5−1x_3 \le x_5 - 1。

我们设 x1=ax_1 = a，则由 (1) x2=ax_2 = a。
由 (3)：x4≥a+1x_4 \ge a+1
由 (4) 和 (5) 得 x4=x5x_4 = x_5，所以 x5≥a+1x_5 \ge a+1。
由 (7)：x5≥a+1x_5 \ge a+1，一致。
由 (2)：x3≤a−1x_3 \le a - 1
由 (6)：x3≤x5−1≥(a+1)−1=ax_3 \le x_5 - 1 \ge (a+1)-1 = a，所以 x3≤ax_3 \le a。
结合 x3≤a−1x_3 \le a-1 和 x3≥1x_3 \ge 1，且 aa 最小可取 11 吗？如果 a=1a=1，则 x3≤0x_3 \le 0 与 x3≥1x_3 \ge 1 矛盾。

所以 aa 必须至少为 2。
取 a=2a=2，则 x1=2,x2=2x_1=2, x_2=2，x3≤1x_3 \le 1，取 x3=1x_3=1。
x4≥3x_4 \ge 3，x5=x4≥3x_5 = x_4 \ge 3，取 x4=3,x5=3x_4=3, x_5=3。

总和 =2+2+1+3+3=11= 2+2+1+3+3=11。

这就是样例的答案 11。

输出：11。

  1. Language
  2. Legacy mode
  3. Theme
  3. Worker 0, 60ms
  4. Powered by Hydro v5.0.0-beta.15 Community