二分图匹配 从第一个开始找匹配 找到第一个无法匹配的break并输出
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N=1010; int help[N][2],from[N],n,m,ans,flag[N]; bool hungary(int x){ for(int i=0;i<=1;i++) { int tmp=help[x][i]; if(flag[tmp]) continue;else flag[tmp]=1; if(!from[tmp] || hungary(from[tmp])){from[tmp]=x;return true;} } return false; } int main(){ //freopen("1191.in","r",stdin);freopen("1191.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d%d",&help[i][0],&help[i][1]); for(int i=1;i<=m;i++){ memset(flag,0,sizeof(flag)); if(hungary(i)) ans++;else break; } printf("%d",ans); return 0; }