1820. Maximum Number of Accepted Invitations

There are m boys and n girls in a class attending an upcoming party.

You are given an m x n integer matrix grid, where grid[i][j] equals 0 or 1. If grid[i][j] == 1, then that means the ith boy can invite the jth girl to the party. A boy can invite at most one girl, and a girl can accept at most one invitation from a boy.

Return the maximum possible number of accepted invitations.

 

Example 1:

Input: grid = [[1,1,1],
               [1,0,1],
               [0,0,1]]
Output: 3
Explanation: The invitations are sent as follows:
- The 1st boy invites the 2nd girl.
- The 2nd boy invites the 1st girl.
- The 3rd boy invites the 3rd girl.

Example 2:

Input: grid = [[1,0,1,0],
               [1,0,0,0],
               [0,0,1,0],
               [1,1,1,0]]
Output: 3
Explanation: The invitations are sent as follows:
-The 1st boy invites the 3rd girl.
-The 2nd boy invites the 1st girl.
-The 3rd boy invites no one.
-The 4th boy invites the 2nd girl.

 

Constraints:

  • grid.length == m
  • grid[i].length == n
  • 1 <= m, n <= 200
  • grid[i][j] is either 0 or 1.

1820. Maximum Number of Accepted Invitations
struct Solution;
use std::collections::VecDeque;

impl Solution {
    fn maximum_invitations(grid: Vec<Vec<i32>>) -> i32 {
        let n = grid.len();
        let m = grid[0].len();
        let mut graph: Vec<Vec<i32>> = vec![vec![0; n + m + 2]; n + m + 2];
        for i in 0..n {
            let u = 0;
            let v = 1 + i;
            graph[u][v] = 1;
        }
        for j in 0..m {
            let u = 1 + n + j;
            let v = 1 + n + m;
            graph[u][v] = 1;
        }
        for i in 0..n {
            for j in 0..m {
                let u = 1 + i;
                let v = 1 + n + j;
                if grid[i][j] == 1 {
                    graph[u][v] = 1;
                }
            }
        }
        let mut res = 0;
        while let Some(path) = bfs(&graph) {
            update(&mut graph, path);
            res += 1;
        }
        res
    }
}

fn bfs(graph: &[Vec<i32>]) -> Option<Vec<usize>> {
    let n = graph.len();
    let mut visited = vec![false; n];
    let mut queue: VecDeque<usize> = VecDeque::new();
    queue.push_back(0);
    visited[0] = true;
    let mut res = vec![0; n];
    while let Some(u) = queue.pop_front() {
        for v in 0..n {
            if !visited[v] && graph[u][v] == 1 {
                visited[v] = true;
                queue.push_back(v);
                res[v] = u;
            }
        }
    }
    if visited[n - 1] {
        Some(res)
    } else {
        None
    }
}

fn update(graph: &mut Vec<Vec<i32>>, path: Vec<usize>) {
    let n = graph.len();
    let mut v = n - 1;
    loop {
        let u = path[v];
        graph[u][v] -= 1;
        graph[v][u] += 1;
        v = u;
        if u == 0 {
            break;
        }
    }
}

#[test]
fn test() {
    let grid = vec_vec_i32![[1, 1, 1], [1, 0, 1], [0, 0, 1]];
    let res = 3;
    assert_eq!(Solution::maximum_invitations(grid), res);
    let grid = vec_vec_i32![[1, 0, 1, 0], [1, 0, 0, 0], [0, 0, 1, 0], [1, 1, 1, 0]];
    let res = 3;
    assert_eq!(Solution::maximum_invitations(grid), res);
}