美文网首页
1820. 最多邀请的个数

1820. 最多邀请的个数

作者: 漫行者_ | 来源:发表于2021-11-27 23:48 被阅读0次

匈牙利算法:

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;
    }

}

相关文章

网友评论

      本文标题:1820. 最多邀请的个数

      本文链接:https://www.haomeiwen.com/subject/cyxfxrtx.html