声明几个定义：
1.二分图
对于一个图G=（V,E），若能将其点集分为两个互不相交的两个子集X、Y，使得X∩Y=∅，且对于G的边集V，若其所有边的顶点全部一侧属于X，一侧属于Y，则称图G为一个二分图。
2.二分图匹配
对于一个二分图G的子图M,若M的边集E的的任意两条边都不连接同一个顶点，则称M为G的一个匹配。
3.最大匹配
对于二分图G的一个子图M，若M为其边数最多的子图，则称M为G的最大匹配。
应用“匈牙利算法”求二分图最大匹配。
这种算法可以这样解释：
建立有向图G，分为二分图的左侧和右侧。
优先选择左侧序号更小的连接可能的边。
若两个点的目标点重复，则递归搜索任意一个点能否更换目标点，若不能则这种匹配无法成立。
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int mp[1010][1010],fri[1010],flg[1010]; int n,m,e,ans=0; int find(int x){ for(int y=1;y<=m;y++) { if(mp[x][y]&&!flg[y]) { flg[y]=1; if(find(fri[y])||!fri[y]) { fri[y]=x; return 1; } } } return 0; } int main() { cin>>n>>m>>e; for(int i=1;i<=e;i++) { int u,v; cin>>u>>v; mp[u][v]=1; } for(int i=1;i<=n;i++) { memset(flg,0,sizeof(flg)); if(find(i)==1) ans++; } cout<<ans; return 0; }