@[suxxsfe](/user/164432) 蛤蛤,您都最大匹配了还有什么增广路啊/fad
by FZzzz @ 2020-05-22 08:26:47
@[FZzzz](/user/174045) 判断一个点一定在最大匹配中,不就是看一下如果强制不匹配它,还能不能有增广路,也就是匹配数和最大匹配数一样?
by suxxsfe @ 2020-05-22 08:36:50
找到增广路就说明不一定在最大匹配中吧
by suxxsfe @ 2020-05-22 08:37:22
@[suxxsfe](/user/164432) 您这样做似乎有一些问题?正确的姿势应该是从某个未盖的 x 点出发走交错路,然后经过的所有 x 点都不一定在匹配中,y 点同理
by FZzzz @ 2020-05-22 08:49:58
@[FZzzz](/user/174045) 大概能明白,但是您说的y点是指哪些点?
而且我这个做法问题在哪呀,感觉这就是把匈牙利的一次bfs再做一遍吧/kel
by suxxsfe @ 2020-05-22 09:15:00
@[suxxsfe](/user/164432) x 和 y 点就是两边的点吧
by FZzzz @ 2020-05-22 09:16:44
@[FZzzz](/user/174045) 懂了懂了
但是我看题解里是再做一遍dfs,那么这样再来一遍bfs也没问题吧,~~然而就是过不了~~
by suxxsfe @ 2020-05-22 09:21:29
@[FZzzz](/user/174045) 大佬我这样写还是不对呀/kk
而且和之前代码的错误输出都是一样的/kk
```cpp
inline void check_(int type_){
tail=0;head=-1;
for(reg int i=1;i<=n*m;i++)
if(!match[i]&&type[i]==type_) que[++head]=i,lost[i]=1;
reg int u,v;
std::memset(check,0,sizeof check);
while(tail<=head){
u=que[tail++];lost[u]=1;
for(reg int i=G.fir[u];i;i=G.nex[i]){
v=G.to[i];
if(check[v]) continue;
check[v]=1;
lost[v]=1;
if(match[v]) que[++head]=match[v];
}
}
}
```
by suxxsfe @ 2020-05-22 09:45:16
判断过程:
```cpp
for(reg int i=1;i<=k;i++){
if(!lost[get_id(xi,xj)]){
xi=read();xj=read();
if(!lost[get_id(xi,xj)]) ans[++ans[0]]=i;
}
else read(),read();
xi=read();xj=read();
}
```
by suxxsfe @ 2020-05-22 09:46:00
那我不会了(
by FZzzz @ 2020-05-22 09:46:23