Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.4 kB
3
Indexable
Never
#include <iostream>
#define ll long long 
using namespace std;

ll n;
ll dem;
ll dem1;
ll arr[101][101];
ll v1[10001], v2[10001], w[10001];
ll nhan[101];
ll cost;

void sort(){
	for(ll i=0; i<dem-1; i++){
		for(ll j=i+1; j<dem; j++){
			if(w[i]<w[j]){
				swap(v1[i], v1[j]);
				swap(v2[i], v2[j]);
				swap(w[i], w[j]);
			}
		}
	}
}

void Kruskal(){
	for(ll i=0; i<dem; i++){
		if(nhan[v1[i]] != nhan[v2[i]]){
			ll nhan1 = min(nhan[v1[i]], nhan[v2[i]]);
			ll nhan2 = max(nhan[v1[i]], nhan[v2[i]]);

			for(ll i=0; i<n; i++){
				if(nhan[i] == nhan2)
					nhan[i] = nhan1;
			}
			cost += w[i];
		}
	}
}

int main(){
	freopen("vao.txt", "r", stdin);
	int t;
	cin >> t;
	for(int tc=1; tc<=t; tc++){
		cin >> n;
		int x, y, z;

		for(ll i=0; i<n; i++){
			for(ll j=0; j<n; j++){
				arr[i][j] = 0;
			}
		}

		ll sum = 0;

		for(ll i=0; i<n; i++){
			cin >> x >> y >> z;
			for(ll j=0; j<z; j++){
				ll m;
				cin >> m;
				arr[x][m] += y;
				arr[m][x] += y;
				sum += y;
			}
		}

		dem = 0, dem1 = 0;
		for(ll i=0; i<n; i++){
			for(ll j=i; j<n; j++){
				if(arr[i][j] != 0){
					v1[dem] = i;
					v2[dem] = j;
					w[dem] = arr[i][j];
					dem++;
				}
			}
		}

		// Dan nhan
		for(ll i=0; i<n; i++){
			nhan[i] = i;
		}

		sort();

		cost = 0;

		Kruskal();

		cout << sum - cost << endl;

	}
	return 0;
}