[模板]二分图最大匹配(匈牙利算法)

P3386 【模板】二分图最大匹配时间限制: 1.00s 内存限制: 512.00MB复制 Markdown中文退出 IDE 模式题目描述给定一个二分图其左部点的个数为 n右部点的个数为 m边数为 e求其最大匹配的边数。左部点从 1 至 n 编号右部点从 1 至 m 编号。输入格式输入的第一行是三个整数分别代表 nm 和 e。接下来 e 行每行两个整数 u,v表示存在一条连接左部点 u 和右部点 v 的边。输出格式输出一行一个整数代表二分图最大匹配的边数。输入输出样例输入 #1复制运行1 1 1 1 1输出 #1复制运行1输入 #2复制运行4 2 7 3 1 1 2 3 2 1 1 4 2 4 1 1 1输出 #2复制运行2说明/提示数据规模与约定对于全部的测试点保证1≤n,m≤500。1≤e≤5×104。1≤u≤n1≤v≤m。不保证给出的图没有重边。#include bits/stdc.h using namespace std; const int N5e35; int a[N], b[N]; vectorinte[N]; bool vis[N]; int match[N]; bool dfs(int u){ for(auto v:e[u]){ if(vis[v])continue; vis[v]1; if(!match[v]||dfs(match[v])){ match[v]u; return 1; } } return 0; } void solve(){ int n,m,q; cinnmq; for(int i1;iq;i){ int u,v; cinuv; e[u].push_back(v); } int ans0; for(int i1;in;i){ memset(vis,0,sizeof vis); if(dfs(i))ans; } coutans\n; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t1; //cint; while(t--)solve(); return 0; }