匈牙利算法:
class Solution {
public int maximumInvitations(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int res = 0;
boolean use[] = new boolean[n];
int[] next = new int[n];
Arrays.fill(next, -1);
for(int i=0; i<m; i++) {
use = new boolean[n];
if(dfs(i, m, n, grid, use, next)) {
res++;
}
}
return res;
}
public boolean dfs(int v, int m, int n, int[][] grid, boolean[] use, int next[]) {
for(int i = 0; i<n; i++) {
if(grid[v][i] == 1 && !use[i]) {
use[i] = true;
if(next[i] == -1 || dfs(next[i], m, n, grid, use, next)) {
next[i] = v;
return true;
}
}
}
return false;
}
}
网友评论