我都调了两三个小时了还没调出来
by suxxsfe @ 2020-05-22 02:30:29
大佬们来帮帮蒟蒻吧
by suxxsfe @ 2020-05-22 02:30:41
`get_id` 就是获取这个点在图中的编号
by suxxsfe @ 2020-05-22 02:31:35
使用 BFS 寻找增广路径，需要记录每个顶点的前驱，以便在后续找到增广路径时根据前驱更新该增广路径上的匹配关系，在您的代码中似乎并未看到更新增广路上各顶点的匹配，还有好几个其他的问题。建议您复习一下匈牙利算法的 BFS 写法，确保正确理解并能口头向别人复述实现细节后再编码，否则容易出错。现在您这个状态去改，只能是在“凑”代码而不是“改”代码。
@[suxxsfe](/user/164432)
by metaphysis @ 2020-05-22 07:23:45
@[metaphysis](/user/333388) 我是已经跑了一遍最大匹配了，然后再对每个点bfs，我觉得这样就只看一下有没有增广路不用更新了吧
by suxxsfe @ 2020-05-22 07:46:17
您说的其它的问题是什么？可能是那些导致的吧
by suxxsfe @ 2020-05-22 07:47:13
我放完整代码吧
```cpp
#define N 1605
#define M 12805
struct graph{
int fir[N],nex[M],to[M],tot;
inline void add(int u,int v){
to[++tot]=v;
nex[tot]=fir[u];fir[u]=tot;
}
}G;
int n,m,tot;
int pre[N],match[N];
int que[N],tail,head,check[N];
int type[N];
int ans[1005],win[2006];
char s[44][44];
const int di[4]={1,-1,0,0};
const int dj[4]={0,0,1,-1};
inline int no(int i_,int j_){return (i_<1||j_<1||i_>n||j_>m);}
inline int get_id(int i,int j){return (i-1)*m+j;}
inline void max_match(){
reg int u,v;
for(reg int i=1;i<=n*m;i++)if(type[i]){
tail=head=0;que[0]=i;
pre[i]=0;
while(tail<=head){
u=que[tail++];
for(reg int j=G.fir[u];j;j=G.nex[j]){
v=G.to[j];
if(check[v]==i) continue;
check[v]=i;
if(match[v]) pre[match[v]]=u,que[++head]=match[v];
else{
int d=u,e=v,t;
while(d){
t=match[d];
match[d]=e;match[e]=d;
d=pre[d];e=t;
}
goto BREAK;
}
}
}
BREAK:;
}
}
inline int bfs(int xi,int xj){
reg int u,v;
u=get_id(xi,xj);
if(!match[u]) return 0;
int tmp=match[u];
tail=0;head=-1;que[++head]=tmp;
std::memset(check,0,sizeof check);check[tmp]=check[u]=1;
match[tmp]=match[u]=0;
int uu=u;
while(tail<=head){
u=que[tail++];
for(reg int i=G.fir[u];i;i=G.nex[i]){
v=G.to[i];
if(check[v]) continue;
check[v]=1;
if(match[v]) que[++head]=match[v];
else goto RETURN;//有增广路
}
}
match[tmp]=uu;match[uu]=tmp;
return 1;
RETURN:;
match[tmp]=uu;match[uu]=tmp;
return 0;
}
int main(){
n=read();m=read();
int xi,xj;
for(reg int i=1;i<=n;i++){
std::scanf("%s",s[i]+1);
for(reg int j=1;j<=m;j++)
if(s[i][j]!='.'){
type[get_id(i,j)]=s[i][j]=='O';
}
else xi=i,xj=j;
}
for(reg int i_,j_,i=1;i<=n;i++){
for(reg int j=1;j<=m;j++){
for(reg int k=0;k<4;k++){
i_=i+di[k];j_=j+dj[k];
if(no(i_,j_)) continue;
if(s[i][j]==s[i_][j_]) continue;
G.add(get_id(i,j),get_id(i_,j_));G.add(get_id(i_,j_),get_id(i,j));
}
}
}
max_match();
int k=read();
for(reg int i=1;i<=k*2;i++){
win[i]=bfs(xi,xj);
xi=read();xj=read();
std::printf(" %d : %d\n",i,win[i]);
}
for(reg int i=1;i<=k;i++)if(win[i*2-1]&&win[i*2]) ans[++ans[0]]=i;
std::printf("%d\n",ans[0]);
for(reg int i=1;i<=ans[0];i++) std::printf("%d\n",ans[i]);
return 0;
}
```
by suxxsfe @ 2020-05-22 07:48:22
@[metaphysis](/user/333388) 您看题啊……这题只是最后跑一遍增广路判断那些点一定在最大匹配中，不是用匈牙利算法求最大匹配……
by FZzzz @ 2020-05-22 07:55:23
@[suxxsfe](/user/164432) 您那里为什么要 `goto RETURN` 啊/kel
by FZzzz @ 2020-05-22 08:16:55
@[FZzzz](/user/174045) `goto RETURN` 找到增广路返回0呀/kel
就是找不找到都要有那两句还原的话，~~懒得写的大括号了~~
by suxxsfe @ 2020-05-22 08:26:17