Deloitte | COGNIZANT | IBM | CAPGEMINI
import java.util.*;
public class TestClass {
public static int cureTheVirus(int n, int[] impact, int[] numOfPre, int[][] precells) {
int source = 0;
int sink = n + 1;
List<Edge>[] graph = new List[sink + 1];
for (int i = 0; i <= sink; i++) {
graph[i] = new ArrayList<>();
}
int totalPositiveImpact = 0;
for (int i = 0; i < n; i++) {
int w = impact[i];
int u = i + 1;
if (w > 0) {
totalPositiveImpact += w;
addEdge(graph, source, u, w);
} else if (w < 0) {
addEdge(graph, u, sink, -w);
}
for (int k = 0; k < numOfPre[i]; k++) {
int v = precells[i][k];
addEdge(graph, u, v, Integer.MAX_VALUE);
}
}
int minCut = dinicMaxFlow(graph, source, sink);
return totalPositiveImpact - minCut;
}
private static class Edge {
int to;
int rev;
int cap;
int flow;
Edge(int to, int rev, int cap) {
this.to = to;
this.rev = rev;
this.cap = cap;
this.flow = 0;
}
}
private static void addEdge(List<Edge>[] graph, int from, int to, int cap) {
Edge a = new Edge(to, graph[to].size(), cap);
Edge b = new Edge(from, graph[from].size(), 0);
graph[from].add(a);
graph[to].add(b);
}
private static int dinicMaxFlow(List<Edge>[] graph, int src, int dest) {
int flow = 0;
int[] level = new int[graph.length];
while (bfs(graph, src, dest, level)) {
int[] ptr = new int[graph.length];
while (true) {
int pushed = dfs(graph, src, dest, Integer.MAX_VALUE, level, ptr);
if (pushed == 0) {
break;
}
flow += pushed;
}
}
return flow;
}
private static boolean bfs(List<Edge>[] graph, int src, int dest, int[] level) {
Arrays.fill(level, -1);
level[src] = 0;
Queue<Integer> q = new LinkedList<>();
q.add(src);
while (!q.isEmpty()) {
int v = q.poll();
for (Edge e : graph[v]) {
if (level[e.to] < 0 && e.flow < e.cap) {
level[e.to] = level[v] + 1;
q.add(e.to);
}
}
}
return level[dest] >= 0;
}
private static int dfs(List<Edge>[] graph, int v, int dest, int pushed, int[] level, int[] ptr) {
if (pushed == 0 v == dest) {
return pushed;
}
for (int cid = ptr[v]; ptr[v] < graph[v].size(); cid = ++ptr[v]) {
Edge e = graph[v].get(cid);
int tr = e.to;
if (level[v] + 1 != level[tr] e.flow == e.cap) {
continue;
}
int trPushed = dfs(graph, tr, dest, Math.min(pushed, e.cap - e.flow), level, ptr);
if (trPushed == 0) {
continue;
}
e.flow += trPushed;
graph[tr].get(e.rev).flow -= trPushed;
return trPushed;
}
return 0;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int numberOfCells = sc.nextInt();
int[] impact = new int[numberOfCells];
int[] numOfPre = new int[numberOfCells];
int[][] precells = new int[numberOfCells][];
for (int j = 0; j < numberOfCells; j++) {
impact[j] = sc.nextInt();
numOfPre[j] = sc.nextInt();
precells[j] = new int[numOfPre[j]];
for (int k = 0; k < numOfPre[j]; k++) {
precells[j][k] = sc.nextInt();
}
}
System.out.println(cureTheVirus(numberOfCells, impact, numOfPre, precells));
sc.close();
}
}
FLIPKART✅
Q3
475 ·