← 返回题目列表

AtCoder · abc328_e

H. 模 MST

中文机器翻译题面 查看原题

分数: 475 点

问题陈述

给您一个加权简单连通无向图,其中 N 顶点和 M 边,其中顶点已编号 1 to N,并且边已编号 1 to M。另外,一个正整数 给出了 K 。
边缘 i\ (1\leq i\leq M) 连接顶点 u_i 和 v_i 的重量为 w_i.

对于生成树 T 该图的成本 T 定义为求和、模 K,中的边的权重 T。 求该图的生成树的最小成本。

约束

  • 2\leq N\leq8
  • N-1\leq M\leq\dfrac{N(N-1)}2
  • 1\leq K\leq10^{15}
  • 1\leq u_i\lt v_i\leq N\ (1\leq i\leq M)
  • 0\leq w_i\lt K\ (1\leq i\leq M)
  • 给定的图很简单且连通。
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

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

输出

打印答案。


样本输入 1

5 6 328
1 2 99
1 3 102
2 3 86
2 4 94
2 5 95
3 4 81

示例输出 1

33

给定的图表如下所示:

包含边的生成树的成本 1,3,5,6 is (99+86+81+95)\bmod{328}=361\bmod{328}=33。 该图的每个生成树的成本至少为 33,所以打印 33.


示例输入 2

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

示例输出 2

325437688

打印该图的唯一生成树的成本,即 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

请注意,输入和答案可能不适合 32\operatorname{bit} 整数。