Untitled

mail@pastecode.io avatar
unknown
plain_text
8 months ago
2.1 kB
1
Indexable
Never
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        for (int t = 1; t <= T; t++) {
            int M = scanner.nextInt();
            Fort[] forts = new Fort[M];
            for (int i = 0; i < M; i++) {
                int id = scanner.nextInt();
                int numStones = scanner.nextInt();
                int numLinks = scanner.nextInt();
                int[] links = new int[numLinks];
                for (int j = 0; j < numLinks; j++) {
                    links[j] = scanner.nextInt();
                }
                forts[i] = new Fort(id, numStones, numLinks, links);
            }
            int minStones = getMinStones(forts);
            System.out.println("Case #" + t);
            System.out.println(minStones);
        }
    }

    public static int getMinStones(Fort[] forts) {
        int M = forts.length;
        int[] stonesNeeded = new int[M];
        for (int i = 0; i < M; i++) {
            boolean[] visited = new boolean[M];
            int stackSize = 0;
            int[] stack = new int[M];
            stack[stackSize++] = i;
            visited[i] = true;
            while (stackSize > 0) {
                int currentFort = stack[--stackSize];
                stonesNeeded[i] += forts[currentFort].numStones;
                for (int neighbor : forts[currentFort].links) {
                    if (!visited[neighbor]) {
                        stack[stackSize++] = neighbor;
                        visited[neighbor] = true;
                    }
                }
            }
        }
        int minStones = 0;
        for (int i = 0; i < M; i++) {
            minStones = Math.max(minStones, stonesNeeded[i]);
        }
        return minStones;
    }
}

class Fort {
    int id;
    int numStones;
    int numLinks;
    int[] links;

    public Fort(int id, int numStones, int numLinks, int[] links) {
        this.id = id;
        this.numStones = numStones;
        this.numLinks = numLinks;
        this.links = links;
    }
}