求助E 朴素贪心挂了
  • 板块学术版
  • 楼主_Fancy_
  • 当前回复14
  • 已保存回复14
  • 发布时间2024/5/4 21:48
  • 上次更新2024/5/5 09:04:29
查看原帖
求助E 朴素贪心挂了
729386
_Fancy_楼主2024/5/4 21:48
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int n, m, tn, sum, root, hv[N];
struct node {
	int k, c;
	vector<int> G;
} a[N];
bool cmp(node x, node y) {
	return x.c < y.c;
}
signed main() {
	scanf("%lld%lld", &n, &m);
	for(int i = 1; i <= m; i++) {
		scanf("%lld%lld", &a[i].k, &a[i].c);
		for(int j = 1, val; j <= a[i].k; j++) scanf("%lld", &val), a[i].G.push_back(val);
	}
	sort(a + 1, a + m + 1, cmp);
	root = a[1].G[0], hv[root] = 1, tn = 1;
	for(int i = 1; i <= m; i++) {
		int nv = 0;
		for(int j = 0; j < a[i].G.size(); j++) {
			if(hv[a[i].G[j]]) {
				nv = 1;
				break;
			}
		}
		if(nv == 0) continue;
		for(int j = 0; j < a[i].G.size(); j++) {
			int tmp = a[i].G[j];
			if(hv[tmp]) continue;
			sum += a[i].c, tn++, hv[tmp] = 1;
			if(tn == n) {
				printf("%lld", sum);
				return 0;
			}
		}
	}
	printf("-1");
	return 0;
}
2024/5/4 21:48
加载中...