# [Jelly], <s>216</s> 208 bytes

    ñ4ñ3ñ1Ɗ_=1ʋƇñ1Ḣ$⁸;ⱮḢ;U$3ịḢ}⁺¦⁹$2¡Wʋ3¦ɼ$02ịñ3ß1Ẹ?Ʋ?ȯƊẸaŒḊ2ƑƲ¿Ẹ
    ịị®$}
    ŒṪ§Ḃ$Ƈṭ+Ø.,UN;$¤fɗ¥€$’Uæ.L‘ṪṬȧ€Ɗ€S,@F0€$ȯ"\ṫ-;@©;L‘$aL$Ɗ,¬ȧ"Tɗɗ/2ịḢç4ç3ç1=®ẈḢ¤ƊƇ,¹Ƈ$Ʋ;ç1‘$Ṫ}Ḣ}¦;F¥¹¹4ƭ€ɼƲ®0;ç1$>/Ʋ?ƲẠ¿Ɗ$T€ṪçÐḟ3Ñ€Ʋṛ®ƲÐL3ịTLH

[Try it online!][TIO-ksda075c]

[Jelly]: https://github.com/DennisMitchell/jelly
[TIO-ksda075c]: https://tio.run/##dVnLbhRXEN3fz0Czi3PANjuLwAplYaUWAWUTKWKRLCJ@IAskzMaRvYFkAVEUkQfYSgJGtiLkMShIPaGF@YuZH3G63X1vnVN3GDR4puf2fVSdOnWq@tuvb9/@7uxsdnh5drg@O1xtd766svp@t93uPs@Pf58sto43FocH3ceNm5P1@avd7tOdxdZJs7fYmk7Wmt@@eL@73uydvp5cWut@7Sd5vDo/Ob7aHl1996Ld6T7eevvD/HhnrX3QHjVvuu@pn@XVbnMwuZO6n6Z/Nfvz43uTdns@ff7R7BFWbn62MWmefHP6sHm6uPdssrj7083ZHjYXdx91g@fTZ@/2u8vtTvff5yvXrl/qx7x7ceHL@fTvjzeuNX9u9CMntzYn7c5K0w2@cOP04enDi2vD5mf7l2f767P91SvNwfzk@@5K86TdabdXmmm7PWmPNrqf@vu7pe70Z232Nq43T5tpM73cPu@WOn3dHePgUj9s8snF7pTt0fzk1@ZNuzO50f3c3Tbbn92fHz9enz3ot3k0n/7cHLRHs/ubvflubH56tvrfm84G/1xZ3P3F1rvPb3@cT/9YbP3bvGxezra7m87ODEhm/dtSAro//ZXzv@Pl84v9GPSfUrLwStYPoHcabvF3Mr1iZdr8ThaujJPqHHxlmIOvDHPQFdqYzpGv@Bx0TL0SDqdz5EmDPdJgqX70YEfeIvKw8SJ88xi@53uGX3pf5I95CNzw4zcyFIpL6IU8JOXviENSvljW4HXK1Mjznf9SFgd0Ot912LTvzW8rs2WQlUXKDvx4tIneHWVhGP/FgEJY/ULy04z7wGj6RKegg6K/x4fDXYsxRPyADBUCCmhJDLPleUC2Q4KjgO5B9hzcbudvijcz3UU/WxougUMDAgooGJBDEWSacY/jwuTzDGuPqHEwAd@BwEslN70vDcvr0B4B3hibxA2FCHb3tKDJzeofM@THgyXxmRwFvCdHd0FAWZmmNWYCuQUQlEWwjmagmIYHbggrH0nwHUBLxmK0Q@DsgBoJH2V3cB/GTWbHJD0xCDWmlFx8kRgkcecSm@XnkpvkFCFY1ZqZtwiqUCpFxmS@L40HABHWeKEgBpEZIp3kEFGkFlcPNJOXJwZkwjTGk6cuC5QZWX7kBGQCFLgUWnEKAyNtgKU4ncxNgKVNekIxyUW@TaHFIQeBJhQfOHboCzKVmt@3hFkRMkQKAUxWhoBLJAU896n1YMGZnk9LzgKdhCfSS4n2XwBZxnkuBcsjUGQgCgiTdUaMZVKjkDEL8cvGLgwDDSUFmzPfGGK0GwpNonwm6ZFhFMDCLAqa8VCJcgmRqEGSB9OlcDIUkybQ9tyWOKpLkggwhkRbCrYV3jRm2AKZGC@gfMT4BqsfhAgPvg6ZA1nMVWEo0S8bOY9KD/wQXuIOzxYpJLeyHEK6dfpJoLSOKkI5x3qyMJUQBV8UWKIxUUIMsMiW4CM6zJM7DxyBYPnNcQo/SxSmwgk51UlK4jwueU4wzUpJqwYNTJ7sfJUUWEd1E0SwOi7C4LJbcQqLd9JNqMSXR1EKR2RGBWcU1F6iSiCVaAQxdw0dkY2xCMo1WG37UOMgShOAZdao4KSUEZWDUCqItnUvJqu0kkYhRxgkHiWlBuFLgSgkzPqJWDbHSdLSRzKl5H0WLqhqTWLSsI1l/sES/2VPBfnAyYk1uIQHgkhKnh2h/FLXK7o3Z5kRN7BoEQQ1zIEGFcCjkhGtE2YCKwgOTS16jXoszlGV1gcqH5iogcrE7F0SFeCEqPSB0hQRhU0RBq4MpVFRpZZUC3olBtQWRyxkso4hXctJr0ptiJ5w@IGAHgALqx0lJWNhhCREBosJDpTVTdK2QCoh1qvCmrAlNTEMFqqLxAlbzV29BYuIthGvkm6FqfoDvc30XMmFkwHQ@gZKc0WRV74Yg4FXXUYorMy8oUGGTHWjAoFQo/dRcVOuIqilECs7yv9V3geFZi14K6@Y9neK9PZBThQV52sloM1HpjBQTAEW@xmhWgUJ7arySgaRzFRYc5IzyYpg4cpd2QpPMlrFnucMT6uJ2niagJdtAeCwIIZLVQbnJqrIR9TNAOmBox7BdEmHjS1SyuFV1c/aUFS9NHk0PJOyMLR5wv1eUL3MmY4VhVkMKe5nizqBVkcFfoGygoJV0yA@X0CRAgjRY8KPEHOwvnSRlNMdrKrTK@gv0@FFCiYPWdRaaLn4WiI/killVYohqAsibM73CaiUWWzQQHomUlFY6NIG@RyJG1XDXvk1kbjResxIllBHqyL83GqKUi0wMncgbBlrcS@JHANIYU8ohvIVgTl5wx/ikWBucEkWi7/ybIXOv6TcQWjEV@yUWyQhi3HsxE4QOA9mICd9LqNHCs9ZJKiIMUCdJEjxHzob7HghRn5IwJcQ0oB9oHKAFlbUPkJ5RiMEF/qOYKr1Z3fSMJS8zyVjIHOETkB5HEtRjdC/W5IlJTXn3r4@VwIkP4S09AHoJFo/FOGo8RcVgD5V1N2QhNT@OSyK2WJTeczHAo57OeAtcaOHpAAvBGn3QJuIFmtRwkYKmV4qgWWPUfmfC9MUnhiaPr/TDnvd6IE8/oo1a5Cr3Bnl/rsHfDI1TrUhsBmCL10fpIo6qjpXggcCRBDfIPhb6/coOOrubZGQJbjjsy6LKVnbum6C/wE "Jelly – Try It Online"

A full program that takes a binary matrix and prints an integer. This generates a bipartite graph and then uses the Hopcroft-Karp method; it’s loosely based on the pseudo code on the Wikipedia page, but obviously has to stick within what’s possible in Jelly. I think it should meet the complexity requirement since the underlying method does, and manages to complete all challenges within about 50 seconds total on TIO.