匈牙利算法 指派问题代码
时间: 2023-10-15 11:03:34 浏览: 53
匈牙利算法是一种用于解决指派问题的算法。以下是匈牙利算法的代码实现:
```java
public class HungaryAlgorithm {
public static int[] assignTasks(int[][] costMatrix) {
int n = costMatrix.length;
int[][] cost = new int[n+1][n+1];
int[][] match = new int[n+1][n+1];
int[] lx = new int[n+1];
int[] ly = new int[n+1];
int[] slack = new int[n+1];
int[] slackx = new int[n+1];
int[] prev = new int[n+1];
int[] S = new int[n+1];
int[] T = new int[n+1];
int[] result = new int[n+1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cost[i][j] = costMatrix[i-1][j-1];
}
}
for (int i = 1; i <= n; i++) {
lx[i] = Integer.MIN_VALUE;
ly[i] = 0;
match[i][0] = 0;
match[0][i] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
lx[i] = Math.max(lx[i], cost[i][j]);
}
}
for (int root = 1; root <= n; root++) {
int[] q = new int[n+1];
int qh = 0, qt = 0;
q[qt++] = root;
for (int i = 0; i <= n; i++) {
prev[i] = 0;
S[i] = 0;
T[i] = 0;
slack[i] = Integer.MAX_VALUE;
}
int x = 0, y = 0;
while (true) {
if (qh == qt) {
while (true) {
int d = Integer.MAX_VALUE;
for (int i = 0; i < qt; i++) {
for (int j = 1; j <= n; j++) {
if (S[j] == 0 && slack[j] < d) {
d = slack[j];
x = q[i];
y = j;
}
}
}
for (int i = 0; i < qt; i++) {
if (S[q[i]] != 0) {
lx[q[i]] -= d;
}
}
for (int j = 1; j <= n; j++) {
if (S[j] == 0) {
slack[j] -= d;
}
}
if (S[y] == 0) {
break;
}
}
if (S[y] == 0) {
break;
}
}
int u = q[qh++];
S[u] = 1;
for (int v = 1; v <= n; v++) {
if (T[v] == 0) {
int delta = lx[u] + ly[v] - cost[u][v];
if (delta < slack[v]) {
slack[v] = delta;
slackx[v] = u;
}
}
}
}
while (true) {
int d = Integer.MAX_VALUE;
for (int i = 1; i <= n; i++) {
if (T[i] == 0 && slack[i] < d) {
d = slack[i];
y = i;
}
}
if (d > 0) {
for (int i = 1; i <= n; i++) {
if (S[i] != 0) {
lx[i] -= d;
}
}
for (int i = 1; i <= n; i++) {
if (T[i] != 0) {
ly[i] += d;
}
}
}
T[y] = 1;
if (match[y][0] == 0) {
break;
}
int x = match[y][0];
q[qt++] = x;
for (int i = 1; i <= n; i++) {
if (cost[x][i] - lx[x] - ly[i] < slack[i]) {
slack[i] = cost[x][i] - lx[x] - ly[i];
slackx[i] = x;
}
}
}
while (true) {
if (qh == qt) {
break;
}
int y = q[qh++];
int x = match[y][0];
match[y][0] = x;
match[x][0] = y;
}
}
for (int i = 1; i <= n; i++) {
result[i-1] = match[i][0] - 1;
}
return result;
}
}
```