题解：P12544 [UOI 2025] Boys and Girls

cosf · 2026-04-28 16:45:36 · 题解

第一眼看成 ARC200E 了还有救吗。

题目相当于给定一张 2n 个点的图，你要从中选出若干条边，使得这些边两两之间都有公共顶点。不难发现只有菊花和三元环符合条件。

菊花是容易的，考虑三元环。对于三元环的三条边 a, b, c，设 a 为其中最大的一条。设 a 的一个端点为 u，那么只有当 a 是 u 的最大出边才有用。这是因为若 a 不是，那么 u 所在的菊花肯定比 a, b, c 三元环更优秀。

考虑枚举 u, a，设 a 的另一端为 v，那么我们可以用一个桶统计所有 v 的出边，然后再枚举 u 的所有出边，看看桶里有没有对应的元素，这样即可在 O(n^2) 内完成本题并通过。

:::success[AC 代码]

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

#define MAXN 1400007

using ll = long long;
using pli = pair<ll, int>;

// 加了快读是因为模拟赛开了 1e7（但不影响 n^2 能过）
char buf[1 << 21], *p1, *p2;

inline char gc()
{
    if (p1 == p2)
    {
        p2 = buf + fread(p1 = buf, 1, sizeof(buf), stdin);
    }
    return *p1++;
}

inline int read()
{
    int x = 0;
    char ch = gc();
    while (ch < '0' || ch > '9')
    {
        ch = gc();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 3) + (x << 1) + (ch ^ '0');
        ch = gc();
    }
    return x;
}

vector<pli> e[MAXN];
ll deg[MAXN];

int n;

ll buc[MAXN];

void solve()
{
    n = read();
    for (int i = 1; i <= 2 * n; i++)
    {
        e[i].clear();
        deg[i] = 0;
    }
    for (int i = 1; i <= n; i++)
    {
        int a = read(), b = read(), c = read();
        e[a].emplace_back(c, b);
        e[b].emplace_back(c, a);
        deg[a] += c;
        deg[b] += c;
    }
    ll res = *max_element(deg + 1, deg + 2 * n + 1);
    for (int i = 1; i <= 2 * n; i++)
    {
        if (e[i].size() < 2)
        {
            continue;
        }
        partial_sort(e[i].begin(), e[i].begin() + 2, e[i].end(), greater<pli>());
        auto a = e[i][0], b = e[i][1];
        if (deg[i] - a.first - b.first >= a.first)
        {
            continue;
        }
        for (auto p : e[a.second])
        {
            buc[p.second] += p.first;
        }
        for (auto b : e[i])
        {
            if (b == a)
            {
                continue;
            }
            res = max(res, b.first + a.first + buc[b.second]);
        }
        for (auto p : e[a.second])
        {
            buc[p.second] = 0;
        }
    }
    cout << res << '\n';
}

int main()
{
    int t = read();
    while (t--)
    {
        solve();
    }
    return 0;
}

虽然通过确实很搞笑。但是卡掉的方法也很容易。注意到这个复杂度应该是 O(\sum \mathit{deg}_i^2) 的，所以只用造一个菊花。不过因为三元环至少要两条出边，菊花会被特判掉，所以造菊花套长度为 2 的链即可。

:::

当然有线性做法。观察到刚才做法复杂度爆炸的地方是枚举 v 的所有出边。所以我们可以直接将所有这样的 u 存进一个 vector 里面，这样对每个 v 只需要统计一次桶了，每个点只用枚举 4 次出边，复杂度 O(n)。

:::success[AC Code]{open}

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

#define MAXN 1400007

using ll = long long;
using pii = pair<int, int>;

char buf[1 << 21], *p1, *p2;

inline char gc()
{
    if (p1 == p2)
    {
        p2 = buf + fread(p1 = buf, 1, sizeof(buf), stdin);
    }
    return *p1++;
}

inline int read()
{
    int x = 0;
    char ch = gc();
    while (ch < '0' || ch > '9')
    {
        ch = gc();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 3) + (x << 1) + (ch ^ '0');
        ch = gc();
    }
    return x;
}

// 模拟赛卡空间 /kx /kx
struct Edge
{
    int u, v, w;
} e[MAXN], g[MAXN];
int eid, gid;
int he[MAXN], hg[MAXN];

ll deg[MAXN];

int n;

int buc[MAXN];

void add(Edge *g, int &gid, int *hg, int u, int v, int w)
{
    g[++gid] = {hg[u], v, w};
    hg[u] = gid;
}

void solve()
{
    n = read();
    for (int i = 1; i <= 2 * n; i++)
    {
        he[i] = 0;
        hg[i] = 0;
        deg[i] = 0;
    }
    for (int i = 1; i <= n; i++)
    {
        int a = read(), b = read(), c = read();
        add(e, eid, he, a, b, c);
        add(e, eid, he, b, a, c);
        deg[a] += c;
        deg[b] += c;
    }
    ll res = *max_element(deg + 1, deg + 2 * n + 1);
    for (int i = 1; i <= 2 * n; i++)
    {
        if (!he[i])
        {
            continue;
        }
        int ma = 0;
        for (int j = he[i]; j; j = e[j].u)
        {
            if (e[j].w > e[ma].w)
            {
                ma = j;
            }
        }
        add(g, gid, hg, e[ma].v, i, e[ma].w);
    }
    for (int i = 1; i <= 2 * n; i++)
    {
        if (!hg[i])
        {
            continue;
        }
        for (int j = he[i]; j; j = e[j].u)
        {
            buc[e[j].v] += e[j].w;
        }
        for (int j = hg[i]; j; j = g[j].u)
        {
            for (int k = he[g[j].v]; k; k = e[k].u)
            {
                if (e[k].v != i)
                {
                    res = max(res, ll(e[k].w) + g[j].w + buc[e[k].v]);
                }
            }
        }
        for (int j = he[i]; j; j = e[j].u)
        {
            buc[e[j].v] = 0;
        }
    }
    cout << res << '\n';
}

int main()
{
    int t = read();
    while (t--)
    {
        solve();
    }
    return 0;
}

:::