题解：P12544 [UOI 2025] Boys and Girls

· · 题解

分析

有 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;
}