dfs里的循环应该是从1到m吧
by WYZ20030051 @ 2023-09-01 16:12:52
@[zhujianheng](/user/941743) 匈牙利算法的外层循环是枚举左部点,内层循环是枚举右部点,所以外层循环从1到n,内层循环从1到m
by WYZ20030051 @ 2023-09-01 16:13:58
全部WA
by zhujianheng @ 2023-09-01 16:14:39
等会儿,我忘记注释了
by zhujianheng @ 2023-09-01 16:15:32
@[zhujianheng](/user/941743) 调好了
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int g[N][N],a[N],b[N],n,m,x,y,k,ans;
bool dfs(int x){
for(int i=1;i<=m;i++){
if(!a[i] && g[x][i]){
a[i]=1;
if(!b[i] || dfs(b[i])){
b[i]=x;
return 1;
}
}
}
return 0;
}
void calcu(){
memset(b,0,sizeof(b));
for(int i=1;i<=n;i++){
memset(a,0,sizeof(a));
if(dfs(i)) ans++;
}
return;
}
int main(){
cin>>n>>m>>k;
for(int i=1;i<=k;i++){
cin>>x>>y;
g[x][y]=1;
}
calcu();
cout<<ans;
return 0;
}
```
by WYZ20030051 @ 2023-09-01 16:16:21
@[zhujianheng](/user/941743) 你统计答案的时候(也就是calcu函数内)不需要cnt这个计数器,直接从1到n枚举左部点,若左部点能够匹配,那么就ans++即可,不需要来回更新最大值
by WYZ20030051 @ 2023-09-01 16:18:04
已A,此贴结
by zhujianheng @ 2023-09-01 19:08:35