# HackerRank Training the army problem solution

In this HackerRank Training the army problem solution Your goal is to design a series of transformations that results in a maximum number of skill sets with a non-zero number of people knowing it.

## Problem solution in Python.

import collections

class Node:
def __init__(self, id_):
self.id = id_
self.residual_flows = {}

INF = 100000

def __init__(self, N_):
self.N = N_

self.node_table = []
for i in range(0, self.N):
self.node_table.append(Node(i))

self.source = 0
self.sink = N_ - 1

self.max_flow = 0

self.main_flows = []

def getMainFlows(self):
net_flows = []
for [u, v, c] in self.main_flows:
net_flows.append([u, v, c, self.node_table[v].residual_flows[u]])
return net_flows

self.node_table[u].residual_flows[v] = c
self.node_table[v].residual_flows[u] = 0

self.main_flows.append([u, v, c])

def addCapacityBoth(self, u, v, c_uv, c_vu):
self.node_table[u].residual_flows[v] = c_uv
self.node_table[v].residual_flows[u] = c_vu

self.main_flows.append([u, v, c_uv])
self.main_flows.append([v, u, c_vu])

def bfs(self):
visited = [False] * self.N

pending = collections.deque();

visited[self.source] = True
pending.append(self.source)

while len(pending) > 0:
curr_node = pending.popleft()

if curr_node == self.sink:
return True

if res_flow > 0 and not visited[adj_node]:

return False

def findMaxFlow(self):
max_total_flow = 0

while self.bfs():

# find maximum possible flow in the BFS path
v = self.sink
while v != self.source:
max_path_flow = min(max_path_flow, self.node_table[u].residual_flows[v])
v = u

# modify the residual flows:
# - remove the flow from residual flows from source to sink
# - add the flow to residual flows from sink to source

v = self.sink
while v != self.source:
self.node_table[u].residual_flows[v] -= max_path_flow
self.node_table[v].residual_flows[u] += max_path_flow
v = u

max_total_flow += max_path_flow

return max_total_flow

[n, k] = list(map(int, input().split()))
C = list(map(int, input().split()))

A = []
B = []

for i in range(0, k):
a = list(map(int, input().split()))
b = list(map(int, input().split()))

A.append(a[1:])
B.append(b[1:])

def getAIdx(w, i):
return sum(len(a) for a in A[:w]) + i + 1 + n*2

def getBIdx(w, i):
return sum(len(a) for a in A) + sum(len(b) for b in B[:w]) + i + 1 + 2*n

# total nodes = 1sink + 1source + 2*N + sum_of_sizes_A + sum_of_sizes_B
total_nodes = 2 + 2 * n + sum(len(a) for a in A) + sum(len(b) for b in B)

for [i, c] in enumerate(C):

for w in range(0, len(A)):
for i in range(0, len(A[w])):

for w in range(0, len(B)):
for i in range(0, len(B[w])):

for w in range(0, len(A)):
for i in range(0, len(A[w])):
for j in range(0, len(B[w])):

print (flow_network.findMaxFlow())

{"mode":"full","isActive":false}

## Problem solution in Java.

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

public class Solution {
private static PrintWriter out;

public static void main(String[] args) throws IOException {
out = new PrintWriter(System.out, true);

int M = in.nextInt(), T = in.nextInt();
N = 2 + M + T * 2;
E = 2 * N + N * T * 2 + T;
flow = new int[2 * E];
capa = new int[2 * E];
now = new int[N];
eprev = new int[2 * E];
elast = new int[N];
level = new int[N];
Arrays.fill (elast, -1);
eidx = 0;

for (int i = 0; i < M; i++) {
int a = in.nextInt();
if (a != 0) {
}
}

for (int i = 0; i < T; i++) {
int num = in.nextInt();
for (int j = 0; j < num; j++) {
add_edge(in.nextInt() - 1, M + i, 1);
}

num = in.nextInt();
for (int j = 0; j < num; j++) {
add_edge(M + i, in.nextInt() - 1, 1);
}

}

out.println(dinic(N - 1, N - 2));
out.close();
System.exit(0);
}

private static int []   flow, capa, now;
public static int[] eadj, eprev, elast;
public static int eidx;
public static int N, E;
public static int INF = 1 << 29;

private static void add_edge (int a, int b, int c) {
flow[eidx] = 0;
capa[eidx] = c;
eprev[eidx] = elast[a];
elast[a] = eidx++;
flow[eidx] = c;
capa[eidx] = c;
eprev[eidx] = elast[b];
elast[b] = eidx++;
}

private static int dinic (int source, int sink) {
int res, flow = 0;
while (bfs (source, sink)) { // see if there is an augmenting path
System.arraycopy (elast, 0, now, 0, N);
while ((res = dfs (source, INF, sink)) > 0) { // push all possible flow through
flow += res;
}
}
return flow;
}

private static int []   level;

private static boolean bfs (int source, int sink) {
Arrays.fill (level, -1);
int front = 0, back = 0;
int [] queue = new int [N];

level[source] = 0;
queue[back++] = source;

while (front < back && level[sink] == -1) {
int node = queue[front++];
for (int e = elast[node]; e != -1; e = eprev[e]) {
if (level[to] == -1 && flow[e] < capa[e]) {
level[to] = level[node] + 1;
queue[back++] = to;
}
}
}
return level[sink] != -1;
}

private static int dfs (int cur, int curflow, int goal) {
if (cur == goal) {
return curflow;
}

for (int e = now[cur]; e != -1; now[cur] = e = eprev[e]) {
if (level[eadj[e]] > level[cur] && flow[e] < capa[e]) {
int res = dfs (eadj[e], Math.min (curflow, capa[e] - flow[e]), goal);
if (res > 0) {
flow[e] += res;
flow[e ^ 1] -= res;
return res;
}
}
}
return 0;
}

final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte[] buffer;

din = new DataInputStream(System.in);
buffer = new byte[BUFFER_SIZE];
}

public Reader(String file_name) throws IOException {
din = new DataInputStream(new FileInputStream(file_name));
buffer = new byte[BUFFER_SIZE];
}

public String readLine() throws IOException {
byte[] buf = new byte[1024];
int cnt = 0, c;
while ((c = read()) != -1) {
if (c == '\n')
break;
buf[cnt++] = (byte) c;
}
return new String(buf, 0, cnt);
}

public int nextInt() throws IOException {
int ret = 0;
while (c <= ' ')
boolean neg = (c == '-');
if (neg)
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}

public long nextLong() throws IOException {
long ret = 0;
while (c <= ' ')
boolean neg = (c == '-');
if (neg)
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}

public double nextDouble() throws IOException {
double ret = 0, div = 1;
while (c <= ' ')
boolean neg = (c == '-');
if (neg)
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (c == '.')
while ((c = read()) >= '0' && c <= '9')
ret += (c - '0') / (div *= 10);
if (neg)
return -ret;
return ret;
}

private void fillBuffer() throws IOException {
buffer[0] = -1;
}

private byte read() throws IOException {
fillBuffer();
return buffer[bufferPointer++];
}

public void close() throws IOException {
if (din == null)
return;
din.close();
}
}
}

{"mode":"full","isActive":false}

## Problem solution in C++.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 10000;
const int MAXM = 100000;
const ll inf = 1LL << 50;

int cnt, box[MAXN], pre[MAXN], gap[MAXN], h[MAXN], cur[MAXN];
int N, NS, NT;
ll flow[MAXN];

struct edge {
int to, ne;
ll w;
} e[MAXM * 2];

void adds(int u, int v, ll w) {
e[cnt].to = v;
e[cnt].w = w;
e[cnt].ne = box[u];
box[u] = cnt++;
}

void add(int u, int v, ll w) {
}

ll mins(ll x, ll y) {
return x < y ? x : y;
}

int qu[MAXN];

void bfs() {
memset(h,-1,sizeof(h));
memset(gap,0,sizeof(gap));
h[NT]=0;
gap[0]=1;
int st=0,ed=1;
qu[ed]=NT;
while(st!=ed) {
int u=qu[++st];
for(int p=box[u]; p!=-1; p=e[p].ne)
if (h[e[p].to]==-1) {
h[e[p].to]=h[u]+1;
qu[++ed]=e[p].to;
++gap[ h[e[p].to]=h[u]+1 ];
}
}
}

ll sap() {
int u,v,p;

ll flowans=0;
//memset(gap,0,sizeof(gap));gap[0]=N;
// memset(h,0,sizeof(h));
bfs();
for(int i=0; i<N; i++) cur[i]=box[i];
flow[NS]=inf;
u=NS;
while(h[NS]<N) {
for(p=cur[u]; p!=-1; p=e[p].ne)
if (e[p].w&&h[e[p].to]+1==h[u]) {
cur[u]=p;
v=e[p].to;
flow[v]=mins(flow[u],e[p].w);
pre[v]=p;
u=v;
if (u==NT) {
flowans+=flow[NT];
while(u!=NS) {
e[pre[u]].w-=flow[NT];
e[pre[u]^1].w+=flow[NT];
u=e[pre[u]^1].to;
}
}
break;
}
if (p==-1) {
cur[u]=box[u];
if (--gap[h[u]]==0) break;
h[u]=N;
for(p=box[u]; p!=-1; p=e[p].ne)
if (e[p].w&&h[e[p].to]+1<h[u])
h[u]=h[e[p].to]+1;
gap[h[u]]++;
if (u!=NS) u=e[pre[u]^1].to;
}
}
return flowans;
}

int main() {
memset(box, -1, sizeof(box));
cnt = 0;
int n, m;
scanf("%d%d", &n, &m);
N = n + m * 2 + 2;
NS = N - 1;
NT = N - 2;
for (int i = 0; i < n; i ++) {
int val;
scanf("%d", &val);
}
int cntx = n;
for (int i = 0; i < m; i ++) {
for (int j = 0; j < 2; j ++) {
int num;
scanf("%d", &num);
for (int k = 0; k < num; k ++) {
int p;
scanf("%d", &p);
if (j == 0) {
} else {
}
}
cntx ++;
}
add(cntx - 2, cntx - 1, inf);
}
printf("%lld\n", sap());
return 0;
}

{"mode":"full","isActive":false}

## Problem solution in C.

#include <stdio.h>
#include <stdlib.h>
typedef struct _node{
int x;
struct _node* next;
} node;
typedef struct _queue{
node *tail;
} queue;
typedef struct _list_node{
int x;
int c;
int *p;
struct _list_node *next;
} list_node;
void ini_q();
void free_q();
void en_q(node *x);
int de_q();
queue q;
list_node **table;

int main(){
int N,T,ALen=0,BLen=0,AC,BC,t,i,j,k,ans=0;
int **A,**B,*C,*AA,*BB,*pp;
node *tt;
list_node *temp;
scanf("%d%d",&N,&T);
A=(int**)malloc(T*sizeof(int*));
B=(int**)malloc(T*sizeof(int*));
C=(int*)malloc(N*sizeof(int));
for(i=0;i<N;i++)
scanf("%d",C+i);
for(i=0;i<T;i++){
scanf("%d",&t);
ALen+=t;
A[i]=(int*)malloc((t+1)*sizeof(int));
A[i][0]=t;
for(j=1;j<=t;j++){
scanf("%d",&A[i][j]);
A[i][j]--;
}
scanf("%d",&t);
BLen+=t;
B[i]=(int*)malloc((t+1)*sizeof(int));
B[i][0]=t;
for(j=1;j<=t;j++){
scanf("%d",&B[i][j]);
B[i][j]--;
}
}
table=(list_node**)malloc((N+ALen+BLen+2)*sizeof(list_node*));
AA=(int*)malloc(ALen*sizeof(int));
BB=(int*)malloc(BLen*sizeof(int));
pp=(int*)malloc((N+ALen+BLen+2)*sizeof(int));
for(i=0;i<N+ALen+BLen+2;i++)
table[i]=NULL;
for(i=0;i<N;i++){
if(C[i])
}
AC=BC=0;
for(i=0;i<T;i++){
for(j=0;j<A[i][0];j++)
for(k=0;k<B[i][0];k++)
if(A[i][j+1]!=B[i][k+1])
for(j=0;j<A[i][0];j++)
AA[AC++]=A[i][j+1];
for(j=0;j<B[i][0];j++)
BB[BC++]=B[i][j+1];
}
for(i=0;i<N;i++){
for(j=0;j<ALen;j++)
if(AA[j]==i)
for(j=0;j<BLen;j++)
if(BB[j]==i)
}
do{
for(i=0;i<N+ALen+BLen+2;i++)
pp[i]=-1;
pp[N+ALen+BLen]=N+ALen+BLen;
ini_q();
tt=(node*)malloc(sizeof(node));
tt->x=N+ALen+BLen;
en_q(tt);
t=de_q();
for(temp=table[t];temp;temp=temp->next)
if(temp->c && pp[temp->x]==-1){
pp[temp->x]=t;
if(temp->x==N+ALen+BLen+1)
goto out;
tt=(node*)malloc(sizeof(node));
tt->x=temp->x;
en_q(tt);
}
}
out:
free_q();
t=N+ALen+BLen+1;
pp[N+ALen+BLen]=-1;
while(pp[t]!=-1){
for(temp=table[pp[t]];temp;temp=temp->next)
if(temp->x==t){
temp->c--;
(*(temp->p))++;
break;
}
t=pp[t];
}
if(pp[N+ALen+BLen+1]!=-1)
ans++;
}while(pp[N+ALen+BLen+1]!=-1);
printf("%d",ans);
return 0;
}
list_node *t1,*t2;
t1=(list_node*)malloc(sizeof(list_node));
t2=(list_node*)malloc(sizeof(list_node));
t1->x=y;
t1->c=c;
t2->x=x;
t2->c=0;
t1->p=&(t2->c);
t2->p=&(t1->c);
list_insert(&table[x],t1);
list_insert(&table[y],t2);
return;
}
return;
}
void ini_q(){
return;
}
void free_q(){
while(p){
t=p;
p=p->next;
free(t);
}
return;
}
void en_q(node *x){
if(!q.tail){
x->next=NULL;
}
else{
q.tail->next=x;
q.tail=x;
q.tail->next=NULL;
}
return;
}
int de_q(){