Untitled

unknown
plain_text
2 months ago
1.4 kB
2
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;
}```