每次匹配前vis要清空
by Serendipity_ly @ 2022-05-26 10:34:37
依旧63pts
by YONIC @ 2022-05-26 20:12:45
```
#include<bits/stdc++.h>
#define N (int)(1e6+3)
using namespace std;
int n,m,ans,match[N];
int vis[N];
vector<int>G[N];
bool connect(int x){
for(int i=0;i<G[x].size();++i){
int y=G[x][i];
if(!vis[y]){
vis[y]=1;
if(!match[y]||connect(match[y])){
match[y]=x;
return 1;
}
}
}
return 0;
}
int main(){
scanf("%d%d",&n,&m);
int u=0,v=0;
while(u>=0){
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
for(int i=1;i<=n;++i) {
memset(vis, 0, sizeof vis);
if(connect(i)) ++ans;
}
printf("%d\n",ans);
for(int i=n+1;i<=m;++i) if(match[i]) printf("%d %d\n",match[i],i);
return 0;
}
```
把vis清空，建双向边
~~是不是有点晚了~~
by florence25 @ 2023-04-26 21:18:03
@[florence25](/user/413370) 不需要双向边，实际上也没用上右集到左集的边
by uneducable @ 2023-07-14 16:38:40