输入文件的一行是两个正整数n和m(0 < n <1001,0 < m < 1001)表示总共有n中“锦囊妙计”，编号为0~n-1，总共有m个问题。
以下的m行，每行两个数，分别表示第m个问题可以使用的“锦囊妙计”的编号。
注意，每种编号的“锦囊妙计”只能使用一次，同一个问题的两个“锦囊妙计”可能一样。
第一行为最多能通过的题数p
#include <stdio.h> #include <math.h> #include <string.h> #include <stdlib.h> #include <iostream> #include <sstream> #include <algorithm> #include <string> #include <queue> #include <map> #include <vector> using namespace std; const int maxn = 1005; const int maxm = 1e4+10; const int inf = 0x3f3f3f3f; const double epx = 1e-10; typedef long long ll; int n,m,k; int visit[maxn]; int match[maxn]; int a[maxn][maxn]; bool found(int x) { for(int i=1; i<=m; i++) //从右边的集合中找能与x进行匹配的点 { if(a[x][i]==1&&visit[i]==0) //x与i有联系且i没被查找过 { visit[i]=1; if(match[i]==0||found(match[i])) //第i个点还没有匹配 如果匹配了就看 与它匹配的那个点 能不能换个点完成匹配 把i空出来 如果可以i与x匹配 { match[i]=x; return true; } } } return false; } int main() { scanf("%d%d",&m,&n); //左右两个集合的数量 memset(a,0,sizeof(a)); for(int i=1; i<=n; i++) { int x,y; scanf("%d %d",&x,&y); a[i][x+1]=1; a[i][y+1]=1; //有联系的点标记为1 } memset(match,0,sizeof(match)); int ans=0; for(int i=1; i<=n; i++) //依次对左边集合中点进行匹配 { memset(visit,0,sizeof(visit)); //清空访问标记数组 if(found(i)) ans++; else break; } printf("%d\n",ans); }
原文：https://www.cnblogs.com/stranger-/p/9813608.html