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;
}