You are the head of a firm and you have to assign jobs to people. You have N persons working under you and you have N jobs that are to be done by these persons. Each person has to do exactly one job and each job has to be done by exactly one person. Each person has his own capability (in terms of time taken) to do any particular job. Your task is to assign the jobs to the persons in such a way that the total time taken is minimum. A job can be assigned to only one person and a person can do only one job.
Example 1:
Input:
N = 2
Arr[] = {3, 5, 10, 1}
Output:
4
Explanation:
The first person takes times 3 and 5
for jobs 1 and 2 respectively. The second
person takes times 10 and 1 for jobs 1 and
2 respectively. We can see that the optimal
assignment will be to give job 1 to person 1
and job 2 to person 2 for a total for 3+1 = 4.
Example 2:
Input:
N = 3
Arr[] = {2, 1, 2, 9, 8, 1, 1, 1, 1}
Output:
3 
Explanation: 
The optimal arrangement would be to assign 
job 1 to person 3,job 2 to person 1 and job 
3 to person 2.
Your Task:
You don't need to read input or print anything. Your task is to complete the function assignmentProblem() which takes an Integer N and an array Arr[] of size N^{2} as input and returns the time taken for the best possible assignment.
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(N^{2})
Constraints:
1 <= N <= 30
1 <= Arr[i] <= 100

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    def assignmentProblem(self, Arr, N):

        # code here 

Solutions:
class Solution:

	def assignmentProblem(self, Arr, N):
		n = N
		l = Arr
		m = []
		mybeg = []
		for i in range(n):
			m.append(l[i * n:(i + 1) * n])
			mybeg.append(l[i * n:(i + 1) * n])

		def util():
			(u, v, ind) = ([0] * n, [0] * n, [-1] * n)
			for i in range(n):
				(links, mins, visited) = ([-1] * n, [1000] * n, [False] * n)
				(marki, markj) = (i, -1)
				while marki != -1:
					j = -1
					for j1 in range(n):
						if not visited[j1]:
							current = m[marki][j1] - u[marki] - v[j1]
							if current < mins[j1]:
								mins[j1] = current
								links[j1] = markj
							if j == -1 or mins[j1] < mins[j]:
								j = j1
					delta = mins[j]
					for j1 in range(n):
						if visited[j1]:
							u[ind[j1]] += delta
							v[j1] -= delta
						else:
							mins[j1] -= delta
					u[i] += delta
					visited[j] = True
					(markj, marki) = (j, ind[j])
				while links[j] != -1:
					ind[j] = ind[links[j]]
					j = links[j]
				ind[j] = i
			return [(ind[j], j) for j in range(n)]
		return sum((mybeg[x][y] for (x, y) in util()))


from collections import deque

class Solution:

	def assignmentProblem(self, Arr, N):
		INF = int(1000000000.0)
		n = 2 * N + 2
		f = [[0 for _ in range(n)] for _ in range(n)]
		s = n - 2
		t = n - 1
		cost = 0
		while True:
			dist = [INF] * n
			dist[s] = 0
			p = [-1] * n
			inq = [False] * n
			q = deque()
			q.append(s)
			while len(q) > 0:
				v = q.popleft()
				inq[v] = False
				if v == s:
					for i in range(N):
						if f[v][i] == 0:
							dist[i] = 0
							p[i] = v
							inq[i] = True
							q.append(i)
				elif v < N:
					for i in range(N, N + N):
						if f[v][i] < 1 and dist[i] > dist[v] + Arr[v * N + i - N]:
							dist[i] = dist[v] + Arr[v * N + i - N]
							p[i] = v
							if not inq[i]:
								inq[i] = True
								q.append(i)
				elif v < N + N:
					for i in range(N):
						if f[v][i] < 0 and dist[i] > dist[v] - Arr[i * N + v - N]:
							dist[i] = dist[v] - Arr[i * N + v - N]
							p[i] = v
							if not inq[i]:
								inq[i] = True
								q.append(i)
			curcost = INF
			for i in range(N):
				if f[i + N][t] == 0 and dist[i + N] < curcost:
					curcost = dist[i + N]
					p[t] = i + N
			if curcost == INF:
				break
			cost += curcost
			cur = t
			while cur != -1:
				pre = p[cur]
				if pre != -1:
					f[pre][cur] = 1
					f[cur][pre] = -1
				cur = pre
		return cost


import collections
import copy
import sys

class HungarianBipartiteMaxMatchingAdjacencyList:

	def __init__(self, graph) -> None:
		self.graph = graph
		self.matching = {}

	def find_match(self, u, visited) -> int:
		for v in self.graph[u]:
			if v not in visited:
				visited[v] = True
				if v not in self.matching or self.find_match(self.matching[v], visited):
					self.matching[v] = u
					return True
		return False

	def max_match(self):
		match_c = 0
		for node in self.graph:
			if self.find_match(node, {}):
				match_c += 1
		return match_c

class VertaxCoverInBipartiteAdjacencyList:

	def __init__(self, bigraph) -> None:
		self.bigraph = bigraph

	def max_matching(self):
		if not hasattr(self, '_max_matching'):
			hungarian = HungarianBipartiteMaxMatchingAdjacencyList(self.bigraph)
			hungarian.max_match()
			self._max_matching = hungarian.matching
		return self._max_matching

	def reverse_matching(self):
		if not hasattr(self, '_reverse_matching'):
			self._reverse_matching = {v: u for (u, v) in self.max_matching().items()}
		return self._reverse_matching

	def koenig_nodes(self):
		visited_setA = {}
		visited_setB = {}
		matching = self.max_matching()
		reverse_matching = self.reverse_matching()

		def alternate_nodes(r):
			visited_setA[r] = True
			for c in self.bigraph[r]:
				if c not in visited_setB:
					visited_setB[c] = True
					alternate_nodes(matching[c])
		for r in self.bigraph:
			if r not in reverse_matching:
				alternate_nodes(r)
		setA_vertices_in_cover = []
		setB_vertices_in_cover = list(visited_setB.keys())
		for r in self.bigraph.keys():
			if r not in visited_setA:
				setA_vertices_in_cover.append(r)
		return (setA_vertices_in_cover, setB_vertices_in_cover)

class Solution:

	def assignmentProblem(self, Arr, N):
		initial_cost_matrix = [[0] * N for i in range(N)]
		for i in range(N * N):
			(r, c) = (i // N, i % N)
			initial_cost_matrix[r][c] = Arr[i]
		cost_matrix = copy.deepcopy(initial_cost_matrix)
		(rows, cols) = (N, N)
		possible_assignements = min(rows, cols)
		matching_size = 0

		def row_reduce(cost_matrix, rows, cols):
			edges_set = set()
			col_set = set()
			for r in range(rows):
				min_val = min(cost_matrix[r])
				for c in range(cols):
					cost_matrix[r][c] -= min_val
					if cost_matrix[r][c] == 0:
						edges_set.add((r, c + rows))
						col_set.add(c)
			return (edges_set, col_set)

		def col_reduce(cost_matrix, rows, cols, edges_set):
			for c in range(cols):
				min_val = sys.maxsize
				for r in range(rows):
					min_val = min(min_val, cost_matrix[r][c])
				for r in range(rows):
					cost_matrix[r][c] -= min_val
					if cost_matrix[r][c] == 0:
						edges_set.add((r, c + rows))

		def get_bigraph(edges_set):
			bigraph = collections.defaultdict(lambda : list())
			for edge in edges_set:
				bigraph[edge[0]].append(edge[1])
			return bigraph

		def bigraph_from_matrix(cost_matrix, rows, cols):
			bigraph = collections.defaultdict(lambda : list())
			for r in range(rows):
				for c in range(cols):
					if cost_matrix[r][c] == 0:
						bigraph[r].append(c + rows)
			return bigraph
		(edges_set, col_set) = row_reduce(cost_matrix, rows, cols)
		if len(col_set) < cols:
			col_reduce(cost_matrix, rows, cols, edges_set)
		bigraph = get_bigraph(edges_set)
		while True:
			vc_helper = VertaxCoverInBipartiteAdjacencyList(bigraph)
			(rows_in_cover, cols_in_cover) = vc_helper.koenig_nodes()
			cover_size = len(rows_in_cover) + len(cols_in_cover)
			if possible_assignements == cover_size:
				res = 0
				for (r1, c1) in vc_helper.reverse_matching().items():
					res += initial_cost_matrix[r1][c1 - rows]
				return res
			else:
				smallest_not_covered = sys.maxsize
				rows_in_cover_map = {i: True for i in rows_in_cover}
				cols_in_cover_map = {i: True for i in cols_in_cover}
				for i in range(rows):
					if i in rows_in_cover_map:
						continue
					for j in range(cols):
						if cost_matrix[i][j] == 0:
							continue
						if j + rows in cols_in_cover_map:
							continue
						smallest_not_covered = min(smallest_not_covered, cost_matrix[i][j])
				for i in rows_in_cover:
					for j in range(cols):
						cost_matrix[i][j] += smallest_not_covered
				for j in range(cols):
					if j + rows in cols_in_cover_map:
						continue
					for i in range(rows):
						cost_matrix[i][j] -= smallest_not_covered
				bigraph = bigraph_from_matrix(cost_matrix, rows, cols)
		return -1


class Solution:

	def assignmentProblem(self, Arr, N):
		n = N
		l = Arr
		m = []
		m_beg = []
		for i in range(n):
			m.append(l[i * n:(i + 1) * n])
			m_beg.append(l[i * n:(i + 1) * n])

		def util():
			(u, v, ind) = ([0] * n, [0] * n, [-1] * n)
			for i in range(n):
				(links, mins, visited) = ([-1] * n, [1000] * n, [False] * n)
				(marked_i, marked_j) = (i, -1)
				while marked_i != -1:
					j = -1
					for j1 in range(n):
						if not visited[j1]:
							current = m[marked_i][j1] - u[marked_i] - v[j1]
							if current < mins[j1]:
								mins[j1] = current
								links[j1] = marked_j
							if j == -1 or mins[j1] < mins[j]:
								j = j1
					delta = mins[j]
					for j1 in range(n):
						if visited[j1]:
							u[ind[j1]] += delta
							v[j1] -= delta
						else:
							mins[j1] -= delta
					u[i] += delta
					visited[j] = True
					(marked_j, marked_i) = (j, ind[j])
				while links[j] != -1:
					ind[j] = ind[links[j]]
					j = links[j]
				ind[j] = i
			return [(ind[j], j) for j in range(n)]
		return sum((m_beg[x][y] for (x, y) in util()))
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		Arr = list(map(int, input().split()))
		ob = Solution()
		print(ob.assignmentProblem(Arr, N))


import numpy as np

class Solution:

	def assignmentProblem(self, Arr, N):
		n = N
		l = Arr
		m = []
		m_beg = []
		for i in range(n):
			m.append(l[i * n:(i + 1) * n])
			m_beg.append(l[i * n:(i + 1) * n])

		def util():
			(u, v, ind) = ([0] * n, [0] * n, [-1] * n)
			for i in range(n):
				(links, mins, visited) = ([-1] * n, [1000] * n, [False] * n)
				(marked_i, marked_j) = (i, -1)
				while marked_i != -1:
					j = -1
					for j1 in range(n):
						if not visited[j1]:
							current = m[marked_i][j1] - u[marked_i] - v[j1]
							if current < mins[j1]:
								mins[j1] = current
								links[j1] = marked_j
							if j == -1 or mins[j1] < mins[j]:
								j = j1
					delta = mins[j]
					for j1 in range(n):
						if visited[j1]:
							u[ind[j1]] += delta
							v[j1] -= delta
						else:
							mins[j1] -= delta
					u[i] += delta
					visited[j] = True
					(marked_j, marked_i) = (j, ind[j])
				while links[j] != -1:
					ind[j] = ind[links[j]]
					j = links[j]
				ind[j] = i
			return [(ind[j], j) for j in range(n)]
		return sum((m_beg[x][y] for (x, y) in util()))


class Solution:

	def assignmentProblem(self, Arr, N):
		n = N
		p = Arr
		pod = []
		mapp = []
		for i in range(n):
			pod.append(p[i * n:(i + 1) * n])
			mapp.append(p[i * n:(i + 1) * n])

		def fun():
			(u, v, ind) = ([0] * n, [0] * n, [-1] * n)
			for i in range(n):
				(links, mins, visit) = ([-1] * n, [1000] * n, [False] * n)
				(i_marked, j_marked) = (i, -1)
				while i_marked != -1:
					j = -1
					for k in range(n):
						if not visit[k]:
							current = pod[i_marked][k] - u[i_marked] - v[k]
							if current < mins[k]:
								mins[k] = current
								links[k] = j_marked
							if j == -1 or mins[k] < mins[j]:
								j = k
					delta = mins[j]
					for k in range(n):
						if visit[k]:
							u[ind[k]] += delta
							v[k] -= delta
						else:
							mins[k] -= delta
					u[i] += delta
					visit[j] = True
					(j_marked, i_marked) = (j, ind[j])
				while links[j] != -1:
					ind[j] = ind[links[j]]
					j = links[j]
				ind[j] = i
			return [(ind[j], j) for j in range(n)]
		return sum((mapp[x][y] for (x, y) in fun()))