分析

有 $n$ 种类型的男孩，每种类型有 $c_i$ 个男孩，他们喜欢两个女孩 $a_i$ 和 $b_i$。要求选出一个最大的男孩集合，使得集合中任意两个男孩至少共同喜欢一个女孩。

将女孩视为顶点，每种类型视为连接 $a_i$ 和 $b_i$ 的边，权值为 $c_i$。问题即为：选择一个边集，使得边集中任意两条边至少有一个公共顶点。这样的边集有两种可能结构：

1. 所有边共享一个公共顶点（下文称“结构 $1$”）。
2. 三条边两两相交，形成一个三角形（下文称“结构 $2$”）。

因此，答案要么是所有与某个顶点相连的边权之和，要么是某个三角形的三条边权之和的最大值。

注：无需考虑重边，因为题目保证女孩对 $(a_i,b_i)$ 互不相同。

思路

1. 建图：顶点数为 $2n$，边数为 $n$，记录每个顶点的度数以及与该顶点相连的边权之和。
2. 计算“结构 $1$”的最大值：只需遍历每个顶点，取边权之和最大值。
3. 计算“结构 $2$”的最大值：
   • 将边定向：对于每条边 $(u,v)$，如果 $deg[u] < deg[v]$ 或（$deg[u] = deg[v]$ 且 $u < v$），则定向为 $u \to v$，否则 $v \to u$。
   • 枚举每个顶点 $v$，标记其所有出边邻居，然后对于每个出边邻居 $u$，枚举 $u$ 的出边邻居 $w$，如果 $w$ 也被 $v$ 标记，则 $(v,u,w)$ 构成“结构 $2$”，计算三条边权之和，更新最大值。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        int V = 2 * n;
        vector<vector<pair<int, ll>>> adj(V + 1);
        vector<ll> sum(V + 1, 0);
        vector<int> deg(V + 1, 0);
        for (int i = 0; i < n; i++) {
            int a, b;
            ll c;
            cin >> a >> b >> c;
            adj[a].push_back({b, c});
            adj[b].push_back({a, c});
            deg[a]++;
            deg[b]++;
            sum[a] += c;
            sum[b] += c;
        }
        // 星型结构的最大值
        ll max_sum = 0;
        for (int v = 1; v <= V; v++) {
            if (sum[v] > max_sum) max_sum = sum[v];
        }
        // 定向：从度数小的点指向度数大的点，度数相同时编号小的指向编号大的
        vector<vector<pair<int, ll>>> out(V + 1);
        for (int v = 1; v <= V; v++) {
            for (auto &[u, c] : adj[v]) {
                if (deg[v] < deg[u] || (deg[v] == deg[u] && v < u)) {
                    out[v].push_back({u, c});
                }
            }
        }
        // 枚举三角形
        vector<int> mark(V + 1, 0);
        vector<ll> weight(V + 1, 0);
        int tag = 0;
        ll max_triangle = 0;
        for (int v = 1; v <= V; v++) {
            if (out[v].size() < 2) continue; // 出度至少为2才可能构成三角形
            tag++;
            // 标记 v 的所有出边邻居，并记录边权
            for (auto &[u, c] : out[v]) {
                mark[u] = tag;
                weight[u] = c;
            }
            // 枚举三角形
            for (auto &[u, c_vu] : out[v]) {
                for (auto &[w, c_uw] : out[u]) {
                    if (mark[w] == tag) {
                        ll total = c_vu + weight[w] + c_uw;
                        if (total > max_triangle) max_triangle = total;
                    }
                }
            }
        }
        cout << max(max_sum, max_triangle) << '\n';
    }
    return 0;
}