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 = {}

class MaxFlow_LinkedList:
    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.parent_links = [-1] * self.N
        
        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
        
    def addCapacity(self, u, v, c):
        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)
        self.parent_links[self.source] = -1
        
        while len(pending) > 0:
            curr_node = pending.popleft()
            
            if curr_node == self.sink:
                return True
            
            for adj_node, res_flow in self.node_table[curr_node].residual_flows.items():
                if res_flow > 0 and not visited[adj_node]:
                    self.parent_links[adj_node] = curr_node
                    pending.append(adj_node)
                    visited[adj_node] = True
                    
        return False
    
    def findMaxFlow(self):
        max_total_flow = 0
        
        while self.bfs():
            
            # find maximum possible flow in the BFS path
            max_path_flow = MaxFlow_LinkedList.INF
            v = self.sink
            while v != self.source:
                u = self.parent_links[v]
                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:
                u = self.parent_links[v]
                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)

flow_network = MaxFlow_LinkedList(total_nodes)

for [i, c] in enumerate(C):
    flow_network.addCapacity(0, i+1, c)
    flow_network.addCapacityBoth(i+1, n+1+i, 1, 1000000)
    flow_network.addCapacity(n+1+i, total_nodes-1, 1)

for w in range(0, len(A)):
    for i in range(0, len(A[w])):
        flow_network.addCapacity(A[w][i], getAIdx(w, i), 1)
        
for w in range(0, len(B)):
    for i in range(0, len(B[w])):
        flow_network.addCapacity(getBIdx(w, i), n+B[w][i], 1)
        
for w in range(0, len(A)):
    for i in range(0, len(A[w])):
        for j in range(0, len(B[w])):
            flow_network.addCapacity(getAIdx(w, i), getBIdx(w, j), 1)
            
print (flow_network.findMaxFlow())

Problem solution in Java.

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

public class Solution {
    private static Reader in;
    private static PrintWriter out;

    public static void main(String[] args) throws IOException {
        in = new Reader();
        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];
        eadj =new int[2 * E];
        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) { 
                add_edge(N - 1, i, a);
            }
            add_edge(i, N - 2, 1);
        }

        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) {
        eadj[eidx] = b; 
        flow[eidx] = 0; 
        capa[eidx] = c; 
        eprev[eidx] = elast[a]; 
        elast[a] = eidx++;
        eadj[eidx] = a; 
        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]) {
                int to = eadj[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;
    }

    static class Reader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

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

        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;
            byte c = read();
            while (c <= ' ')
            c = read();
            boolean neg = (c == '-');
            if (neg)
            c = read();
            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;
            byte c = read();
            while (c <= ' ')
            c = read();
            boolean neg = (c == '-');
            if (neg)
            c = read();
            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;
            byte c = read();
            while (c <= ' ')
            c = read();
            boolean neg = (c == '-');
            if (neg)
            c = read();
            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 {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
            buffer[0] = -1;
        }

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

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

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) {
    adds(u, v, w);
    adds(v, u, 0LL);
}

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);
        add(NS, i, val);
        add(i, NT, 1);
    }
    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) {
                    add(p - 1, cntx, 1);
                } else {
                    add(cntx, p - 1, 1);
                }
            }
            cntx ++;
        }
        add(cntx - 2, cntx - 1, inf);
    }
    printf("%lldn", sap());
    return 0;
}

Problem solution in C.

#include <stdio.h>
#include <stdlib.h>
typedef struct _node{
  int x;
  struct _node* next;
} node;
typedef struct _queue{
  node *head;
  node *tail;
} queue;
typedef struct _list_node{
  int x;
  int c;
  int *p;
  struct _list_node *next;
} list_node;
void add_edge(int x,int y,int c);
void list_insert(list_node **head,list_node *x);
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])
      add_edge(N+ALen+BLen,i,C[i]);
    add_edge(i,N+ALen+BLen+1,1);
  }
  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])
          add_edge(N+AC+j,N+ALen+BC+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)
        add_edge(i,N+j,1);
    for(j=0;j<BLen;j++)
      if(BB[j]==i)
        add_edge(N+ALen+j,i,1);
  }
  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);
    while(q.head){
      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;
}
void add_edge(int x,int y,int c){
  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;
}
void list_insert(list_node **head,list_node *x){
  x->next=*head;
  *head=x;
  return;
}
void ini_q(){
  q.head=q.tail=NULL;
  return;
}
void free_q(){
  node *p=q.head,*t;
  while(p){
    t=p;
    p=p->next;
    free(t);
  }
  return;
}
void en_q(node *x){
  if(!q.tail){
    q.head=q.tail=x;
    x->next=NULL;
  }
  else{
    q.tail->next=x;
    q.tail=x;
    q.tail->next=NULL;
  }
  return;
}
int de_q(){
  int x=q.head->x;
  node *p=q.head;
  q.head=q.head->next;
  if(q.head==NULL)
    q.tail=NULL;
  free(p);
  return x;
}