AT_abc308_h [ABC308Ex] Make Q

题目描述

有一个包含 $N$ 个顶点、$M$ 条边的简单无向图，最开始所有的边都是白色的。顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$，将这条边涂成黑色需要花费 $C_i$ 的代价。

通过将至少 $4$ 条边涂成黑色，并满足以下所有条件的操作，称为“构造 Q”：

• 除了一条黑色边以外，其余所有黑色边恰好构成一个简单环。
• 那条不在上述环中的黑色边，连接了属于该环的顶点和不属于该环的顶点。

请判断是否可以构造 Q，如果可以，请求出构造 Q 所需的最小总代价；如果不可以，输出 $-1$。

输入格式

输入按以下格式从标准输入读入：

$N$ $M$
$A_1$ $B_1$ $C_1$
$A_2$ $B_2$ $C_2$
$\vdots$
$A_M$ $B_M$ $C_M$

输出格式

如果可以构造 Q，则输出构造 Q 所需的最小总代价；如果不可以，输出 $-1$。

输入输出样例 #1

输入 #1

5 6
1 2 6
2 3 4
1 3 5
2 4 3
4 5 2
3 5 1

输出 #1

15

输入输出样例 #2

输入 #2

4 4
1 2 1
2 3 1
3 4 1
1 4 1

输出 #2

-1

输入输出样例 #3

输入 #3

6 15
2 6 48772
2 4 36426
1 6 94325
3 6 3497
2 3 60522
4 5 63982
4 6 4784
1 2 14575
5 6 68417
1 5 7775
3 4 33447
3 5 90629
1 4 47202
1 3 90081
2 5 79445

输出 #3

78154

说明/提示

限制条件

• $4 \leq N \leq 300$
• $4 \leq M \leq \frac{N(N-1)}{2}$
• $1 \leq A_i < B_i \leq N$
• 若 $i \neq j$，则 $(A_i, B_i) \neq (A_j, B_j)$
• $1 \leq C_i \leq 10^5$
• 所有输入均为整数

样例解释 1

将第 $2,3,4,5,6$ 条边涂成黑色时：

• 边 $2,4,5,6$ 恰好构成一个简单环；
• 边 $3$ 连接了顶点 $3$（属于上述环）和顶点 $1$（不属于上述环）；

因此，总代价为 $4+5+3+2+1=15$，可以构造 Q。用其他方法构造 Q 的总代价也不会小于 $15$，所以答案为 $15$。

由 ChatGPT 4.1 翻译