题意
给定一个有 \(n\) 个点的图，初始没有任何边。接下来有 \(m\) 次操作，每次操作给定一个大小为 \(k\) 的集合 \(S\) 和一个权值 \(c\)，并对所有 \(u,v \in S\) 并且 \(u < v\) 的点 \(u,v\) 连上一条边权为 \(c\) 的边。\(m\) 次操作后，判断图的连通性，若图联通则需求出其最小生成树的边权总和。
思路
如果直接暴力建边，时间复杂度 \(O(n^2)\)，不可接受。
仔细思考一下，其实发现并不需要这么多的边。具体地，对于一个大小为 \(k\) 的集合 \(S\)，只需要连 \(k-1\) 条边。为什么呢？假设只有这 \(k\) 个点要求最小生成树，那么最后一定只选择 \(k-1\) 条边。换句话说，在求最小生成树的过程中，只要保证对于同一个 \(S\) 中的点有足够的边能够选择即可。
有了上面的结论后，这道题就不难了。先使用并查集判断连通性，再使用 Kruskal 或 Prim 算法求最小生成树即可。时间复杂度 \(O(n \log n)\)。
代码如下：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define int long long
using namespace std;
int n,m,cnt,c,a,b,fa[1000001];
int tot,ans;
struct E
{
int u,v,w;
}e[1000001];
int cx( int x )
{
if( x == fa[x] ) return x;
return fa[x] = cx( fa[x] );
}
bool ck( void )
{
int f = cx( 1 );
for( int i = 2 ; i <= n ; i ++ )
if( cx( i ) != f )
return false;
return true;
}
bool cmp( E x , E y )
{
return x.w < y.w;
}
signed main()
{
cin >> n >> m;
for( int i = 1 ; i <= n ; i ++ )
fa[i] = i;
while( m -- )
{
cin >> cnt >> c;
cin >> a;
for( int i = 2 ; i <= cnt ; i ++ )
{
cin >> b;
fa[cx( b )] = cx( a );
tot ++;
e[tot].u = a,e[tot].v = b,e[tot].w = c;
}
}
if( !ck() )
{
cout << -1 << endl;
return 0;
}
sort( e + 1 , e + tot + 1 , cmp );
cnt = 0;
for( int i = 1 ; i <= n ; i ++ )
fa[i] = i;
for( int i = 1 ; i <= tot ; i ++ )
{
int x = cx( e[i].u ),y = cx( e[i].v );
if( x == y ) continue;
fa[x] = y;
ans += e[i].w;
cnt ++;
if( cnt == n - 1 ) break;
}
cout << ans;
return 0;
}