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

    ñ4ñ3ñ1Ɗ_=1ʋƇñ1Ḣ$⁸;ⱮḢ;U$3ịḢ}⁺¦⁹$2¡Wʋ3¦ɼ$02ịñ3ß1Ẹ?Ʋ?ȯƊẸaŒḊ2ƑƲ¿Ẹ
    ịị®$}
    FJṁ×⁸Z,$ṖŻż"ḊƲ€Z,¥/Ẏ€;"/×¹Ƈ¥"ŒJ§ḂƊaFƊ0€,$ṫ-;1aL$,¬ȧ"Tɗʋ/;©$2ịḢç4ç3ç1=®ẈḢ¤ƊƇW;¹ƇƊƲ;ç1‘$Ṫ}Ḣ}¦;¹¹4ƭ€ɼƲ®0;ç1$>/Ʋ?ƲẠ¿ƊT€ṪçÐḟ3Ñ€Ʋṛ®ƲÐL3ịTLH

[Try it online!][TIO-ksdoc3bi]

[Jelly]: https://github.com/DennisMitchell/jelly
[TIO-ksdoc3bi]: https://tio.run/##dVnLahxXEN3fzxCzdI4sybvB8c4EY6iNg8Gb4EU2wT@QhcHyRmEEwXYgDoTgvGyRl4JEMBrZxNATNbb/YuZHlG5131vn1B3bDOrpuX0fVadOnar@4vN79748P18cXVkc7SyOttrZZ1e33u@3e9318uTnyWr3ZLo6Ouwup59Odpav9rur@6vd0@bFanc@2W5@uv1@f6d58e715PJ292s/ybOt5enJtfb42tu/21l3effsyfJktt0@bo@bN9331M/yar85nNxP128s57uLp90qdy5NlvNvz16dvd7oRrfHq4d/3rnUPN9cnn7dXU43NhdPm3m71zzfOHtyozlYnjxsZ3evt7PL3a/9o398NN26e3Nyqfnz7cHGrXdP3@9vTpvfJtvDlhcHVxYHO4uDravN4fL0q@5O82s7a/duT/tJu6vjaffj6sF33Uy/3@/P2LzofmrmV9q/ugXeve72fni5HzP5eLM7Wnu8PP2xedPObnW/do8sDhaPlifPdhaPu@/dj/Pvm8P2ePHoZm@yWzc/Od/670137n@urh78YDvd9dk3y/kvq91/m5fNy8Ve99D5uQHJrP9YSkD3p79z8Xe8fXGzH4P@KiUL/5L1A@iThkf8k0zvWJk2f5KFO@OkOgffGebgO8McdIc2pnPkOz4HHVPvhMPpHHnSYI80WKofPdiRt4g8bLwJ3zyG7/mZ4ZfeF/kyD4EbfvxGhkJxCf1DHpLyd8QhKd8sa/A6ZWrk@S5@KYsDOp3vOmza9@aPldkyyMoiZQd@PNpE746yMIz/YkAhrP6H5KcZ94HR9IlOQQdF/4wPh7sWY4j4ARkqBBTQkhhmy/OAbIcERwE9g@w5uN0uPhRvZrqLfrY03AKHBgQUUDAghyLINOMex4XJ5xnWHlHjYAK@A4GXSm56XxqW16E9ArwxNokbChHs7mlBk5vVLzPkx4Ml8ZkcBbwnR3dBQFmZpjVmAnkEEJRFsI5moJiGB24IKx9J8B1AS8ZitEPg7IAaCR9ld3Afxk1mxyQ9MQg1ppRcfJEYJHHnEpvl55Kb5BQhWNWambcIqlAqRcZkfi6NBwAR1nijIAaRGSKd5BBRpBZXDzSTlycGZMI0xpOnLguUGVl@5ARkAhS4FFpxCgMjbYClOJ3MTYClTXpCMclFvk2hxSEHgSYUHzh26AsylZo/t4ZZETJECgFMVoaASyQFPPep9WDBmZ5PS84CnYQn0luJ9l8AWcZ5LgXLI1BkIAoIk3VGjGVSo5AxC/HLxi4MAw0lBZsz3xhitBsKTaJ8JumRYRTAwiwKmvFQiXIJkahBkgfTpXAyFJMm0PbcljiqS5IIMIZEWwq2Fd40ZtgCmRgvoHzE@AarH4QID74OmQNZzFVhKNEvG7mISg/8EF7iDs8WKSS3shxCunX6SaC0jipCOcd6sjCVEAVfFFiiMVFCDLDIluAjOsyTOw8cgWD5zXEKP0sUpsIJOdVJSuI8LnlOMM1KSasGDUye7GKVFFhHdRNEsDouwuCyW3EKi3fSTajEl0dRCkdkRgVnFNReokoglWgEMXcNHZGNsQjKNVht@1DjIEoTgGXWqOCklBGVg1AqiLZ1LyartJJGIUcYJB4lpQbhS4EoJMz6iVg2x0nS0kcypeR9Fi6oak1i0rCNdf7BGv9lTwX5wMmJNbiEB4JISp4dofxS1yu6N2eZETewaBEENcyBBhXAo5IRrRNmAisIDk0teo16LM5RldYHKh@YqIHKxOxdEhXghKj0gdIUEYVNEQauDKVRUaWWVAt6JQbUFkcsZLKOIV3LSa9KbYiecPiBgB4AC6sdJSVjYYQkRAaLCQ6U1U3StkAqIdarwpqwNTUxDBaqi8QJW81dfQSLiLYRr5Juhan6A33M9FzJhZMB0PoGSnNFkVe@GIOBV11HKKzMvKFBhkx1owKBUKP3UXFTriKopRArO8r/Vd4HhWYteCuvmPZ3ivT2QU4UFedrJaDNR6YwUEwBFvsZoVoFCe2q8koGkcxUWHOSM8mKYOHKXdkKTzJaxZ7nDE@ridp4moDXbQHgsCCGS1UG5yaqyEfUzQDpgaMewXRJh40tUsrhVdXP2lBUvTR5NDyTsjC0ecL9XlC9zJmOFYVZDCnuZ4s6gVZHBX6BsoKCVdMgvl9AkQII0WPCjxBzsL50kZTTHayq0yvor9PhRQomD1nUWmi9@FojP5IpZVWKIagLImzO9wmolFls0EB6JlJRWOjSBvkciRtVw175NZG40XrMSJZQR6si/NxqilItMDJ3IGwda3EviRwDSGFPKIbyFYE5ecMf4pFgbnBJFou/8m6Fzr@m3EFoxFfslFskIYtx7MROEDgPZiAnfS@jRwrvWSSoiDFAnSRI8R86G@x4IUZ@ScC3ENKAfaBygBZW1D5CeUcjBBf6jmCq9Xd30jCUvM8lYyBzhE5AeR1LUY3Qv1uTJSU1596@vlcCJD@EtPQB6CRaPxThqPEXFYC@VdTdkITU/jksitliU3nNxwKOezngLXGjh6QALwRp90CbiBZrUcJGCpleKoF1r1H5vwvTFN4Ymr6/0w573eiBvP6KNWuQq9wZ5f67B3wyNU61IbAZgi9dH6SKOqo6V4IHAkQQ3yD4W@v3KDjq7m2RkCW447suiylZ27pugv8B "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 28 seconds total on TIO.