solve this question in java

Problem restatement (what the screenshots describe)

1. Input

   text
   n                               // number of tunnels   ( 1 < n ≤ 100 )
   n lines with n entries (0 / 1)  // adjacency matrix of the tunnels
   maintenanceCost[0 … n-1]        // last line, n integers ( 0 < cost ≤ 10^6 )

   adj[i][j] = 1 means tunnel i and tunnel j are directly connected.

2. Super tunnel – a tunnel whose collapse makes at least one other tunnel unreachable.
   In graph theory that is exactly an articulation point (cut-vertex).

3. Output – a single integer:

   Σ maintenanceCost[i]   for every tunnel i that is a super tunnel
   

---

Algorithm

The classic way to find all articulation points in an undirected graph is the Tarjan (DFS-time/low-link) algorithm, O(n + m) where m is the number of edges (here m ≤ n(n-1)/2, still tiny for n ≤ 100).

During one depth-first search we record for every vertex u:

symbol	meaning
disc[u]	discovery time of u
low[u]	the minimum disc reachable from u via a single back-edge or children
parent[u]	DFS parent of u
children	how many DFS tree children root u has

Rules for an articulation point u

• Root of a DFS tree and children > 1
• Non-root and for some child v, low[v] ≥ disc[u]

Finally sum the maintenance costs of all vertices flagged as articulation points.

Space: O(n + m); n ≤ 100, well inside limits.

---

Correctness proof (sketch)

Lemma 1 If a vertex u is marked by Tarjan’s test above, removing u disconnects at least one vertex from u’s component.

Proof.
Case A u is root with > 1 DFS children.
Each child subtree has no back-edge to the root or another child (or it would have been visited earlier). Deleting the root eliminates the only path between those subtrees, disconnecting the graph.

Case B u is non-root and some child v has low[v] ≥ disc[u].
Then no vertex in v’s subtree has a back-edge to an ancestor of u. Every path from that subtree to the rest of the graph passes through u; deleting u isolates it. ∎

Lemma 2 If a vertex u is not marked, the graph remains connected after removing u.

Proof.
If u is root, children ≤ 1, so all other vertices are still connected through that single child.
If u is non-root, for every child v, low[v] < disc[u]. There is a back-edge from v’s subtree to an ancestor of u, hence an alternative path circumventing u. ∎

Theorem Vertices reported by the algorithm are exactly the super tunnels; summing their given costs yields the required project cost.

From Lemma 1 every reported vertex is a super tunnel; from Lemma 2 every super tunnel is reported. Summing their costs therefore produces precisely the total maintenance cost required. ∎

---

Complexity analysis

Building adjacency lists O(n²) (from the matrix).
DFS / Tarjan O(n + m); with n ≤ 100 this is at most ~10 000 operations.
Memory O(n + m), negligible for the limits.

---

Reference implementation (Java 17)

java
import java.io.*;
import java.util.*;

public class Main {
    static int n;                       // number of tunnels
    static List<Integer>[] g;           // adjacency list
    static long[] cost;                 // maintenance cost
    static int time;                    // DFS time counter
    static int[] disc, low, parent;     // Tarjan arrays
    static boolean[] ap;                // articulation point flags

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine().trim());

        // build graph
        @SuppressWarnings("unchecked")
        List<Integer>[] tmp = new ArrayList[n];
        for (int i = 0; i < n; i++) tmp[i] = new ArrayList<>();
        g = tmp;

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                int v = Integer.parseInt(st.nextToken());
                if (v == 1 && i != j) {   // undirected edge
                    g[i].add(j);
                }
            }
        }

        // costs
        cost = new long[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            cost[i] = Long.parseLong(st.nextToken());
        }

        // Tarjan setup
        time = 0;
        disc = new int[n];
        low = new int[n];
        parent = new int[n];
        Arrays.fill(parent, -1);
        ap = new boolean[n];

        // run DFS in every component
        boolean[] visited = new boolean[n];
        for (int u = 0; u < n; u++) {
            if (!visited[u]) {
                dfs(u, visited);
            }
        }

        // sum maintenance cost of super tunnels
        long total = 0;
        for (int i = 0; i < n; i++) {
            if (ap[i]) total += cost[i];
        }
        System.out.println(total);
    }

    private static void dfs(int u, boolean[] visited) {
        visited[u] = true;
        disc[u] = low[u] = ++time;
        int children = 0;

        for (int v : g[u]) {
            if (!visited[v]) {
                parent[v] = u;
                children++;
                dfs(v, visited);

                // update low value
                low[u] = Math.min(low[u], low[v]);

                // articulation tests
                if (parent[u] == -1 && children > 1)
                    ap[u] = true;
                if (parent[u] != -1 && low[v] >= disc[u])
                    ap[u] = true;
            } else if (v != parent[u]) {          // back edge
                low[u] = Math.min(low[u], disc[v]);
            }
        }
    }
}

Compile & run example

sh
javac Main.java
java Main < input.txt

The program reads from STDIN, writes only the required total cost to STDOUT, and satisfies all stated constraints.