Hungarian algorithm
unknown
c_cpp
3 years ago
1.2 kB
10
Indexable
pair<long long, vector<int>> hungarianAlgorithm(vector<vector<long long>> a) { int n = a.size() - 1; int m = a[0].size() - 1; vector<int> pl(n + 1, 0), pr(n + 1, 0), mt(n + 1, 0), way(n + 1, 0); for (int row = 1; row <= n; row++) { mt[0] = row; vector<int> minv(n + 1, INT_MAX); vector<bool> used(n + 1, false); int col = 0; do { used[col] = true; int v = mt[col], delta = INT_MAX, nextcol; for (int i = 1; i <= n; i++) { if (used[i]) continue; int x = a[v][i] - pl[v] - pr[i]; if (x < minv[i]) minv[i] = x, way[i] = col; if (minv[i] < delta) delta = minv[i], nextcol = i; } for (int i = 0; i <= n; i++) { if (used[i]) pl[mt[i]] += delta, pr[i] -= delta; else minv[i] -= delta; } col = nextcol; } while (mt[col] != 0); do { int nextcol = way[col]; mt[col] = mt[nextcol]; col = nextcol; } while (col); } vector<int> res(n+1); for (int i = 1; i <= m; i++) res[mt[i]] = i; return { -pr[0],res }; }
Editor is loading...