问题重述

有 $n$ 种类型的男生，第 $i$ 种类型有 $c_i$ 个男生，每个这样的男生喜欢两个特定的女生 $(a_i, b_i)$。总共有 $2n$ 个女生。

我们需要找到一个最大的男生集合，满足：集合中任意两个男生至少有一个共同喜欢的女生。

问题转化与建模

图论模型

将问题抽象为图论模型：

• 女生作为顶点，共有 $2n$ 个
• 每种男生类型对应一条连接两个女生的边 $(a_i, b_i)$，该边有权重 $c_i$（表示这种类型的男生数量）

问题转化为：选择一些边，并为每条边选择一个非负整数 $t_i \le c_i$（表示选择该类型的男生数量），使得选择的边集满足：任意两条被选中的边（$t_i > 0$ 的边）必须共享至少一个公共顶点。

我们要最大化 $\sum t_i$。

核心观察与分析

基本结构分析

设选择的边集为 $E'$，对应的选择数量为 $t_i$。条件要求：对于 $E'$ 中任意两条边 $e_1, e_2$，都有 $e_1 \cap e_2 \neq \emptyset$（即共享至少一个端点）。

关键引理：满足上述条件的边集 $E'$ 只能是以下三种结构之一：

1. 星形结构：所有边共享一个公共顶点
2. 两条边结构：两条边共享一个公共顶点
3. 三角形结构：三条边分别连接三个顶点，形成三角形

结构证明概要

1. 如果 $|E'| = 1$：显然满足条件。
2. 如果 $|E'| = 2$：两条边必须共享一个顶点才能满足条件。
3. 如果 $|E'| = 3$：有三种可能：
   • 三条边共享一个顶点（星形）
   • 两条边共享一个顶点，第三条边与其中一条共享另一个顶点（实际上是星形的变种）
   • 三条边连接三个顶点，每两条边共享一个不同的顶点，形成三角形
4. 如果 $|E'| \ge 4$：可以证明，如果四条或更多边两两有公共顶点，那么它们必须共享一个公共顶点。否则无法满足条件。

直观理解：考虑四条边 $e_1, e_2, e_3, e_4$，如果它们两两有交但无公共交点，那么每条边必须与其他三条边都有交点。由于每条边只有两个端点，这需要复杂的配置，最终会导出矛盾。

分类解法

基于上述结构分析，我们分别处理三种情况：

情况1：星形结构（所有边共享一个公共顶点）

对于每个女生 $v$（即每个顶点），考虑所有与 $v$ 相连的边。这些边天然满足条件，因为都经过 $v$。

因此，对于顶点 $v$，最大可选男生数量为：

$$\text{Star}(v) = \sum_{i: a_i = v \text{ 或 } b_i = v} c_i $$

我们需要对所有顶点 $v$ 计算该值并取最大值。

情况2：两条边结构

考虑两条边 $e_1 = (u,v)$ 和 $e_2 = (u,w)$，它们共享顶点 $u$。这两条边满足条件。

对于给定的共享顶点 $u$，我们选择与 $u$ 相连的权重最大的两条边。设与 $u$ 相连的边按权重降序排列为 $w_1 \ge w_2 \ge \cdots$，则：

$$\text{Pair}(u) = w_1 + w_2$$

需要注意：两条边可能实际上是同一条（即连接同一对顶点的边），但根据题目条件，每种男生类型喜欢的女生组合唯一，所以不存在多条边连接同一对顶点。

情况3：三角形结构

三角形由三个顶点 $u, v, w$ 和三条边 $(u,v), (v,w), (u,w)$ 组成。任意两条边共享一个顶点。

设三条边的权重分别为 $c_{uv}, c_{vw}, c_{uw}$，则三角形结构最多可选择：

$$\text{Triangle}(u,v,w) = c_{uv} + c_{vw} + c_{uw} $$

这是因为我们可以选择所有三种类型的男生。

算法设计与优化

基本算法框架

1. 读取输入，建立图结构，记录每条边的权重
2. 计算星形结构的最大值
3. 计算两条边结构的最大值
4. 计算三角形结构的最大值
5. 输出三者中的最大值

计算星形结构

直接遍历所有顶点，计算与其相连的所有边的权重之和。时间复杂度 $O(n)$。

计算两条边结构

对于每个顶点 $u$，找到与 $u$ 相连的权重最大的两条边。可以通过维护最大堆或简单排序实现。总时间复杂度 $O(n \log d_{\max})$，其中 $d_{\max}$ 是最大度数。

计算三角形结构（关键优化）

朴素方法：枚举所有三元组 $(u,v,w)$，检查三条边是否存在。时间复杂度 $O((2n)^3) = O(n^3)$，不可接受。

优化思路：

• 由于总边数为 $n \le 7 \times 10^5$，度数总和为 $2n$
• 采用"按度数排序"的枚举策略

具体方法： 对于每条边 $(u,v)$，选择 $u$ 和 $v$ 中度数较小的顶点（设为 $u$）。枚举 $u$ 的所有邻居 $w$，检查边 $(v,w)$ 是否存在。

复杂度分析：

• 对于边 $(u,v)$，设 $\deg(u) \le \deg(v)$
• 枚举 $u$ 的所有邻居 $w$，复杂度 $O(\deg(u))$
• 总复杂度为 $\sum_{(u,v)} \min(\deg(u), \deg(v))$

可以证明该复杂度为 $O(n \sqrt{n})$：

• 如果 $\deg(u) \le \sqrt{n}$，那么贡献为 $O(\sqrt{n})$
• 如果 $\deg(u) > \sqrt{n}$，那么这样的顶点 $u$ 最多有 $O(\sqrt{n})$ 个（因为度数总和为 $2n$），每条边最多贡献 $O(\sqrt{n})$

因此总复杂度 $O(n \sqrt{n})$，对于 $n \le 7 \times 10^5$ 可接受。

正确性证明概要

1. 完备性：我们考虑了所有可能满足条件的边集结构（星形、两条边、三角形），没有遗漏。
2. 最优性：对于每种结构，我们都计算了可能的最大值。
3. 充分性：如果存在满足条件的男生集合，那么它对应的边集必定属于这三种结构之一。

特殊情况处理

1. 重边问题：题目保证对于任意 $i \ne j$，$(a_i, b_i) \ne (a_j, b_j)$，所以没有重边。
2. 大权重处理：$c_i$ 可达 $10^9$，需要使用 64 位整数（long long）。
3. 内存管理：使用邻接表存储图，避免邻接矩阵的内存爆炸。

复杂度总结

• 时间复杂度：$O(n \sqrt{n})$，主要来自三角形枚举
• 空间复杂度：$O(n)$，存储图结构

总结

本题的核心在于将组合条件转化为图论条件，并通过结构分析发现只有三种基本结构满足要求。通过分类计算这三种情况的最大值，我们得到了问题的完整解法。复杂度优化技巧（按度数枚举）是处理大规模图问题的常用方法，确保了算法在实际约束下的可行性。

这种"分析结构 + 分类处理 + 优化枚举"的解题思路在图论和组合问题中具有普遍适用性，是解决复杂约束优化问题的有效方法。