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.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 = 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);
}
``````