Untitled

mail@pastecode.io avatar
unknown
plain_text
6 days ago
3.0 kB
1
Indexable
Never
import java.util.*;

class Canh {
    int dau, cuoi, trongso;
}

public class Main {
    static long ntest, m;
    static long[] d = new long[101];
    static int[] dad = new int[101];
    static Canh[] CA = new Canh[10001];
    static long chiphi = 0;
    static int dem = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        ntest = sc.nextInt();
        for (int j = 1; j <= ntest; j++) {
            m = sc.nextInt();
            chiphi = 0;
            dem = 0;
            for (int jj = 1; jj <= m; jj++) {
                int i = sc.nextInt();
                int u = sc.nextInt();
                int c = sc.nextInt();
                d[i] = u;
                dad[i] = -1;
                for (int j1 = 1; j1 <= c; j1++) {
                    int v = sc.nextInt();
                    if (i > v) {
                        dem++;
                        CA[dem] = new Canh();
                        CA[dem].dau = i;
                        CA[dem].cuoi = v;
                        CA[dem].trongso = (int)(d[i] + d[v]);
                        chiphi += CA[dem].trongso;
                    }
                }
            }
            process();
            System.out.println("Case" + j);
            System.out.println(chiphi);
        }
        sc.close();
    }

    static int findDad(int u) {
        if (dad[u] == -1) {
            dad[u] = u;
            return u;
        }
        return dad[u];
    }

    static void add(int u, int v) {
        if (u > v) {
            for (int i = 1; i <= m; i++) {
                if (dad[i] == u) {
                    dad[i] = v;
                }
            }
        } else if (v > u) {
            for (int i = 1; i <= m; i++) {
                if (dad[i] == v) {
                    dad[i] = u;
                }
            }
        }
    }

    static void quickSort(Canh[] CA, int l, int r) {
        if (l < r) {
            int key = CA[(l + r) / 2].trongso;
            int i = l, j = r;
            while (i <= j) {
                while (CA[i].trongso < key) i++;
                while (CA[j].trongso > key) j--;
                if (i <= j) {
                    if (i < j) {
                        Canh g = CA[i];
                        CA[i] = CA[j];
                        CA[j] = g;
                    }
                    i++;
                    j--;
                }
            }
            quickSort(CA, l, j);
            quickSort(CA, i, r);
        }
    }

    static void process() {
        quickSort(CA, 1, dem);
        int demcanh = 0, demdinh = 0;
        int i1 = dem, x, y;
        while (demcanh < m - 1 && demdinh < m) {
            x = findDad(CA[i1].dau);
            if (x == -1) demdinh++;
            y = findDad(CA[i1].cuoi);
            if (y == -1) demdinh++;
            if (x != y) {
                add(x, y);
                demcanh++;
                chiphi -= CA[i1].trongso;
            }
            i1--;
        }
    }
}
Leave a Comment