[ABC352E]题解

merlinkkk / 2024-07-17 / 原文

思路

这里提供一种暴力做法。方法就是当边数到达一个值过后就不加边了。我取的值是 $500000$，实际上可以开大一些，只要 $x \log x$ 不超时就行了。

代码

赛时提交记录

#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[200020];
int cnt;
struct rec
{
    int x, y, z;
} edge[5000010];
int fa[500010];
bool operator<(rec a, rec b)
{
    return a.z < b.z;
}
int get(int x) { return fa[x] == x ? x : fa[x] = get(fa[x]); }
signed main()
{
    cin.tie(0), cout.tie(0);
    ios::sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int k, c;
        cin >> k >> c;
        for (int i = 1; i <= k; i++)
        {
            cin >> a[i];
        }
        if(cnt>5000000) continue;
        for (int i = 1; i < k; i++)
        {
            for (int j = i + 1; j <= k; j++)
            {
                int u = a[i], v = a[j];
                if(cnt>5000000) break;
                edge[++cnt] = {u, v, c};
                
            }
            if(cnt>5000000) break;
        }
    }
    sort(edge + 1, edge + cnt + 1);
    for(int i=1;i<=n;i++) fa[i]=i;
    int ans = 0;
    for (int i = 1; i <= cnt; i++)
    {
        int x = get(edge[i].x),
            y = get(edge[i].y);
        if (x == y)
            continue;
        fa[x] = y;
        ans += edge[i].z;
    }
    int flag = 0;
    for (int i = 1; i <= n; i++)
        if (fa[i] == i)
            flag++;
    if (flag > 1)
        cout << "-1";
    else
        cout << ans;
    return 0;
}