P12544 [UOI 2025] Boys and Girls

思路

将问题转化为图论模型。

把每个女孩看成一个点，每种男孩看成一条边：

• 男孩类型 $i$ 对应边 $(a_i,b_i)$；
• 边权为 $c_i$。

题目要求选择最大的男孩集合，使得任意两个被选择的男孩至少喜欢同一个女孩。

等价于：

在一张带权图中，选择一个最大权边集，使得任意两条边都有公共端点。

---

关键性质

对于一个简单图，如果一个边集合中的任意两条边都有公共端点，那么这个集合只有两种情况。

情况 1：所有边经过同一个点

例如：

    1
   /|\
  / | \
 2  3  4

所有边都有公共点 $1$。

这种情况对应：

选择某个女孩，所有喜欢她的男孩都可以加入。

设女孩 $i$ 的贡献为：

$$sum_i=\sum_{e\ni i}w_e$$

直接统计所有女孩即可。

---

情况 2：三角形

例如：

1
/ \
2---3

三条边：

$$(1,2),(2,3),(1,3)$$

任意两条边都有公共点。

因此还需要考虑所有三角形的边权和。

---

三角形枚举

直接枚举三个点会超时。

采用经典的按度数定向。

定义：

$$(deg_u,u)<(deg_v,v)$$

将边从较小的点指向较大的点。

对于一个点 $u$，枚举：

$$u\rightarrow v$$

然后枚举：

$$v\rightarrow x$$

如果存在：

$$u\rightarrow x$$

则：

$$(u,v,x)$$

构成三角形。

---

复杂度

设边数为 $m=n$。

统计所有星形：

$$O(n)$$

枚举三角形：

$$O(n\sqrt n)$$

空间复杂度：

$$O(n)$$

---

C++代码

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct Edge {
    int a, b;
    ll c;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        int n;
        cin >> n;

        int m = 2 * n;

        vector<Edge> e(n);
        vector<int> deg(m + 1);
        vector<ll> sum(m + 1);

        for (int i = 0; i < n; i++) {
            int a, b;
            ll c;
            cin >> a >> b >> c;

            e[i] = {a, b, c};

            deg[a]++;
            deg[b]++;

            sum[a] += c;
            sum[b] += c;
        }

        ll ans = 0;

        for (int i = 1; i <= m; i++)
            ans = max(ans, sum[i]);

        auto cmp = [&](int a, int b) {
            if (deg[a] != deg[b]) return deg[a] < deg[b];
            return a < b;
        };

        vector<vector<pair<int,ll>>> g(m + 1);

        for (auto [a, b, c] : e) {
            if (cmp(b, a)) swap(a, b);
            g[a].push_back({b, c});
        }

        vector<ll> vis(m + 1, -1);

        for (int u = 1; u <= m; u++) {
            vector<int> tmp;

            for (auto [v, w] : g[u]) {
                vis[v] = w;
                tmp.push_back(v);
            }

            for (auto [v, w1] : g[u]) {
                for (auto [x, w2] : g[v]) {
                    if (vis[x] != -1)
                        ans = max(ans, w1 + w2 + vis[x]);
                }
            }

            for (int x : tmp)
                vis[x] = -1;
        }

        cout << ans << '\n';
    }

    return 0;
}