Submit Info #48957

Problem Lang User Status Time Memory
Assignment Problem python3 ansain AC 314 ms 40.41 MiB

ケース詳細
Name Status Time Memory
example_00 AC 185 ms 27.75 MiB
hand_minus_00 AC 314 ms 40.41 MiB
hand_plus_00 AC 310 ms 40.34 MiB
max_random_00 AC 251 ms 39.97 MiB
max_random_01 AC 249 ms 39.93 MiB
max_random_02 AC 250 ms 39.85 MiB
max_random_03 AC 251 ms 39.89 MiB
max_random_04 AC 248 ms 39.88 MiB
random_00 AC 189 ms 29.55 MiB
random_01 AC 195 ms 29.70 MiB
random_02 AC 188 ms 28.16 MiB
random_03 AC 193 ms 29.49 MiB
random_04 AC 182 ms 27.65 MiB

from scipy.optimize import linear_sum_assignment import numpy as np #バグり散らかしたけど一応記録として残しておく 参考:http://yasutech.blogspot.com/2012/07/hangarian-algorithm.htmldef hangarian2(n, calc): def hangarian2(n, calc): while True: calc = (calc.T-np.min(calc, axis=1)).T calc -= np.min(calc, axis=0) row_ind = np.full(n, -1) col_ind = np.full(n, -1) zeroc = np.where(calc == 0, 0, 1) while np.min(calc[np.ix_(np.where(row_ind == -1)[0], np.where(col_ind == -1)[0])]) == 0: for row in range(n): tmp = np.where( (np.where(calc[row] == 0, 1, 0)*np.where(col_ind == -1, 1, 0)) == 1)[0] if tmp.shape[0] == 1: col_ind[tmp[0]] = row zeroc[row][tmp[0]] = 2 for col in range(n): tmp = np.where( (np.where(calc[:, col] == 0, 1, 0)*np.where(row_ind == -1, 1, 0)) == 1)[0] if tmp.shape[0] == 1: row_ind[tmp[0]] = col zeroc[tmp[0]][col] = 2 #print(row_ind,col_ind) #print(calc) if np.min(row_ind)==0: return row_ind,np.arange(n) if np.min(col_ind)==0: return np.arange(n),col_ind row_mark = np.full(n, 0) col_mark = np.full(n, 0) m = np.arange(n) m2 = np.where(np.max(zeroc[:, m], axis=1) != 2)[0] #print(zeroc,m2,calc) if m2.shape[0] == 0: return np.argmax(zeroc, axis=1), m row_mark[m2] = 1 while True: # 1:それ以外 2:仮決めの0 0:取り消しの0 m = np.where(np.min(zeroc[m2], axis=0) == 0)[0] if m.shape[0] == 0: break col_mark[m] = 1 m2 = np.where(np.max(zeroc[:, m], axis=1) == 2)[0] if m2.shape[0] == 0: break row_mark[m2] = 1 tmp = np.min( calc[np.ix_(np.where(row_mark == 1)[0], np.where(col_mark == 0)[0])]) calc[np.ix_(np.where(row_mark == 1)[0], np.where(col_mark == 0)[0])] -= tmp calc[np.ix_(np.where(row_mark == 0)[0], np.where(col_mark == 1)[0])] += tmp # print(calc) # break n=int(input()) cost = np.array([list(map(int, input().split())) for i in range(n)]) row_ind, col_ind = linear_sum_assignment(cost) print(cost[row_ind,col_ind].sum()) ans=[0]*n for a,b in zip(row_ind,col_ind): ans[a]=b print(*col_ind)