Description

Link：CF875F

Solution

将王子抽象成点，将公主抽象成边。对于一个公主，设其备选的两个王子为 $x, y$，需要的嫁妆为 $z$。连一条无向边 $(x, y, z)$。

一条边需要和这条边的一个端点配对，一个端点只能与与其相连的一条边配对。可以理解为每个节点至多选择一条出边，故选出的每个连通块要么是树、要么是基环树。故本题要求的是最大生成基环树森林。

考虑 Kruskal，对于一条边 $(x, y, z)$，当且仅当以下情况可以加入：

• $x, y$ 不连通，且 $x, y$ 所在的连通块不能均为基环树。
• $x, y$ 连通，且所在的连通块不为基环树（但是加入这条边之后，所在的连通块就变成基环树了）。

使用并查集维护连通性，再额外记录一下每个连通块是否为基环树即可。