2025年 北马其顿编程竞赛 (Macedonian programming contests 2025)

赛事等级： 社区与地区级竞赛 (Community and Regional competition)
内容类型： 竞赛题目 (Competition tasks)

题目名称：校赛结果 (Резултати од училишен натпревар)

题目描述

如你所知，在学校竞赛中通常没有公开的排名表，但每个学生都很有兴趣将自己的成绩与其他人的成绩进行比较。

两名学生之间的联系可以是直接的，也可以是间接的。如果两名学生可以直接互相交流，则联系是直接的。如果学生 $X$ 与 $Y$ 有联系，且 $Y$ 与 $Z$ 有联系，那么我们认为 $X$ 通过联系“网络”与 $Z$ 建立了间接联系。

直接联系有时会很“棘手”，因为有些学生在与其他学生交流时，并不会尽力精确地传递信息。有时在特定的沟通中，甚至会故意传递错误的信息。

因此，对于所有现有的直接沟通，引入了一个衡量信息传输质量的数值评分，称为准确度指数 (Accuracy Index, IT)。该指数可以是任何整数（负数表示信息传输质量非常差）。

共有 $N$ 名学生参加比赛，编号为 $1$ 到 $N$。目前已建立总计 $M$ 个直接联系，每个联系由值 $A_i, B_i$ 和 $C_i$ 描述，表示学生 $A_i$ 和 $B_i$ 可以直接交流，其准确度指数为 $C_i$。

学生们希望为明年仅选择部分直接联系来构建一个网络，使得每个人都能与其他人取得联系（直接或间接）。同时，他们希望这个网络尽可能“可靠”，即希望找到一个具有最大可能总准确度指数（网络中每个参与的直接联系的 $IT$ 之和）的网络。

你的任务是编写一个程序，计算可以形成的“最可靠网络”的总准确度指数。如果无法建立一个让每个人都能互相联系的网络，则应输出 "N"。

输入格式

• 第一行包含两个整数：$N$ ($2 \le N \le 100,000$) 和 $M$ ($0 \le M \le 200,000$)，分别表示学生人数和联系数量。
• 接下来的 $M$ 行，每行包含三个整数：$A_i, B_i$ 和 $C_i$ ($1 \le A_i, B_i \le N, A_i \neq B_i, -10^6 \le C_i \le 10^6$)，表示学生 $A_i$ 和 $B_i$ 之间存在直接联系，准确度指数为 $C_i$。
• 两个学生之间最多描述一个直接联系（例如，不会同时出现 $(1, 2, 10)$ 和 $(2, 1, 7)$）。

评分说明：

• 15% 的分数满足：$N \le 10, M \le 10$，且 $C_i < 0$。
• 另有 15% 的分数满足：$N \le 1,000, M \le 2,000$，且 $C_i < 0$。
• 另有 30% 的分数满足：$N \le 1,000, M \le 2,000$。

输出格式

• 输出一个整数，代表最可靠网络的最高可能总准确度指数；如果无法形成完整的网络，则输出 "N"。

限制条件

• 时间限制： 400 毫秒
• 内存限制： 64 MB

样例说明

样例 1： 输入：

4 5
1 2 -1 
2 3 -5 
3 4 -3 
4 1 -2 
4 2 -3

输出：-6 解释：通过选择 (1, 2) IT=-1, (3, 4) IT=-3, (4, 1) IT=-2 建立网络，总 IT = -6。

样例 2： 输入：

5 4
1 2 5 
2 3 2 
3 1 -1 
4 5 0

输出：N 解释：学生 {1, 2, 3} 无法与 {4, 5} 取得联系。

版权信息

• 项目： Macedonian Programming Contests 2025
• 赛事： Community and Regional competition
• 版权方： ZIM (北马其顿计算机科学家协会)