Untitled
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; }