NC20052. [HNOI2006]超级英雄HERO
描述
输入描述
输入文件的一行是两个正整数n和m(0 < n < 1001,0 < m < 1001)表示总共有n中“锦囊妙计”，编号为0~n-1，总共有m个问题。 以下的m行，每行两个数，分别表示第m个问题可以使用的“锦囊妙计”的编号。 注意，每种编号的“锦囊妙计”只能使用一次，同一个问题的两个“锦囊妙计”可能一样。
输出描述
第一行为最多能通过的题数p
示例1
输入:
5 6 3 2 2 0 0 3 0 4 3 2 3 2
输出:
4
C++ 解法, 执行用时: 5ms, 内存消耗: 4344K, 提交时间: 2021-07-13 17:33:51
#include<bits/stdc++.h>
using namespace std;
int e[1010][1010],b[1010],match[1010],n,m;
int dfs(int u){
for(int i=1;i<=n;i++){
if(b[i]==0&&e[u][i]==1){
b[i]=1;
if(match[i]==0||dfs(match[i])){
match[i]=u;
return 1;
}
}
}
return 0;
}
int main(){
cin>>n>>m;
int x,y,sum=0;
for(int i=1;i<=m;i++){
cin>>x>>y;
e[i][x+1]=1;
e[i][y+1]=1;
}
int i;
for(i=1;i<=m;i++){
memset(b,0,sizeof b);
if(dfs(i)==0)
break;
}
cout<<i-1;
return 0;
}