AT_abc328_e.[ABC328E] Modulo MST

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个有 $N$ 个顶点、 $M$ 条边的带权无向连通简单图，顶点编号为 $1$ 到 $N$ ，边编号为 $1$ 到 $M$ ，以及一个正整数 $K$ 。
第 $i$ 条边 $(1\leq i\leq M)$ 连接顶点 $u_i$ 和顶点 $v_i$ ，权值为 $w_i$ 。

对于该图的任意一棵生成树 $T$ ，定义 $T$ 的代价为 $T$ 所包含的所有边的权值之和对 $K$ 取模后的结果。
请你求出所有生成树的代价的最小值。

输入格式

输入按以下格式从标准输入给出。

$N$ $M$ $K$
$u_1$ $v_1$ $w_1$
$u_2$ $v_2$ $w_2$
$\vdots$
$u_M$ $v_M$ $w_M$

输出格式

请输出答案。

输入输出样例

输入#1

输出#1

输入#2

6 5 998244353
1 2 337361568
1 6 450343304
2 3 61477244
2 5 745383438
4 5 727360840

输出#2

325437688

输入#3

8 28 936294041850197
1 2 473294720906780
1 3 743030800139244
1 4 709363019414774
1 5 383643612490312
1 6 557102781022861
1 7 623179288538138
1 8 739618599410809
2 3 857687812294404
2 4 893923168139714
2 5 581822471860662
2 6 740549363586558
2 7 307226438833222
2 8 447399029952998
3 4 636318083622768
3 5 44548707643622
3 6 307262781240755
3 7 12070267388230
3 8 700247263184082
4 5 560567890325333
4 6 704726113717147
4 7 588263818615687
4 8 549007536393172
5 6 779230871080408
5 7 825982583786498
5 8 713928998174272
6 7 751331074538826
6 8 449873635430228
7 8 11298381761479

输出#3

11360716373

说明/提示

限制条件

$2\leq N\leq 8$
$N-1\leq M\leq\dfrac{N(N-1)}{2}$
$1\leq K\leq 10^{15}$
$1\leq u_i < v_i \leq N\ (1\leq i\leq M)$
$0\leq w_i < K\ (1\leq i\leq M)$
给定的图是简单且连通的
所有输入均为整数

样例解释 1

给定的图如下所示。

包含边 $1,3,5,6$ 的 $4$ 条边的生成树的代价为 $(99+86+81+95)\bmod{328}=361\bmod{328}=33$ 。
该图所有生成树的代价都不小于 $33$ ，因此输出 $33$ 。

样例解释 2

该图只有一棵生成树，其代价为 $325437688$ ，请输出该值。

样例解释 3

请注意，输入和答案可能超出 $32$ 位整数的范围。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页