求助T~T莫名WA
查看原帖
求助T~T莫名WA
987758
CaoSheng_zzz楼主2024/9/10 11:01
#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <bitset>
#include <queue>
#include <map>
#include <set>
#define prt printf
#define ll long long
#define spc putchar(' ')
#define ent putchar('\n')
#define pr_ prt("---")
#define prx prt("***")
#define prtn (putchar('N') , putchar('o'))
#define prty (putchar('Y') , putchar('e') , putchar('s'))
using namespace std;

inline int read(){
	int f = 1 , k = 0;
	char c = getchar();
	while(c < '0' || c > '9'){
		if(c == '-') f = -1;
		c = getchar() ;
	}
	while(c >= '0' && c <= '9'){
		k = (k << 3) + (k << 1) + (c ^ 48);
		c = getchar() ;
	}
	return (f == 1 ? k : -k);
}

void output(ll now){
	if(now < 0){
		putchar('-');
		output(- now);
	}
	else{
		if(now > 9) output(now / 10);
		putchar((now % 10) ^ 48);
	}
}

const int maxn = 2e5 + 1 , maxm = 2e5 + 1 ;
int n , m , tot ;
ll ans ;
int fa[maxn] ;
struct edge {
	ll val ; vector<int> d ; //定义
	bool operator < (const edge &a) { return val < a.val ;} //重载运算符
}a[maxn];

inline int find(int u) { return fa[u] == u ? fa[u] : fa[u] = find(fa[u]) ;} //并查集

signed main() {
	n = read() , m = read() ; 
	for(int i=1 ; i<=m ; i++) { //读入
		int k = read() ; a[i].val = read() ;
		while(k --) a[i].d.push_back(read()) ;
	}
	for(int i=1 ; i<=n ; i++) fa[i] = i ;
	sort(a + 1 , a + m + 1) ;
	for(int i=1 ; i<=m ; i++) { //计算
		int u = a[i].d.front() , fu = find(u) ;
		for(auto v : a[i].d) { //kruskal板子
			int fv = find(v) ;
			if(fu != fv) {
//				output(u) , spc , output(v) , spc , output(a[i].val) , ent;
				++ tot , fa[fu] = fv , ans += a[i].val ;
				if(tot == n - 1) return output(ans) , 0 ;
			}
		}
	}
	return puts("-1") , 0 ;
}
2024/9/10 11:01
加载中...