仅5pts求助
查看原帖
仅5pts求助
609565
OtterZ楼主2024/1/3 20:34

本人检查很久没发现问题,结果 WA 5pts,仅 #1 AC。

#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int tot_node = 1609;
vector<int>e[tot_node];//边 
int mat[tot_node];//匹配节点 
bool vis[tot_node];//不撞环
int del;//试图删掉 
bool H_srh(int v){//匈牙利算法的搜索
	for(int i = 0; i < e[v].size(); i ++){
		if(vis[e[v][i]] || e[v][i] == del)
			continue;
		vis[e[v][i]] = true;
		if(mat[e[v][i]] == 0 || H_srh(mat[e[v][i]])){//可以匹配
			mat[e[v][i]] = v,mat[v] = e[v][i];//匹配
			vis[e[v][i]] = false;
			return true;
		}
	} 
	return false;
} 
int n,m,c[49][49],x,y,k;
//这个网格将白格和其它构成二分图 
int blk(int _x,int _y){//格子对应的点
	return (_x - 1) * m + _y; 
}
vector<int>f;
bool lf,nf;
void f0(){
	if(mat[blk(x,y)] == 0){
		nf = false;
	}
	else{
		del = blk(x,y);
		mat[mat[blk(x,y)]] = 0;
		memset(vis,false,sizeof(bool) * (n * m + 1));
		if(H_srh(mat[blk(x,y)])){
			nf = false;
			mat[blk(x,y)] = 0;//去匹配 
		}
		else{
			nf = true;
			mat[mat[blk(x,y)]] = blk(x,y);
		}
	}
}
void f1(){
	if(mat[blk(x,y)] == 0){
		lf = false;
	}
	else{
		del = blk(x,y);
		mat[mat[blk(x,y)]] = 0;
		memset(vis,false,sizeof(bool) * (n * m + 1));
		if(H_srh(mat[blk(x,y)])){
			lf = false;
			mat[blk(x,y)] = 0;//去匹配 
		}
		else{
			lf = true;
			mat[mat[blk(x,y)]] = blk(x,y);
		}
	}
}
int main(){
	scanf("%d %d",&n,&m);
	for(int i = 1; i <= n; i ++){
		for(int j = 1; j <= m; j ++){
			scanf(" %c",&c[i][j]);
			if(c[i][j] == 'O'){
				if(i > 1 && c[i - 1][j] != 'O'){//向上建边 
					e[blk(i,j)].push_back(blk(i - 1,j));
					e[blk(i - 1,j)].push_back(blk(i,j));
				}
				if(j > 1 && c[i][j - 1] != 'O'){//向左建边 
					e[blk(i,j)].push_back(blk(i,j - 1));
					e[blk(i,j - 1)].push_back(blk(i,j));
				}
			}
			else{
				if(c[i][j] == '.'){
					x = i,y = j;
				}
				if(i > 1 && c[i - 1][j] == 'O'){//向上建边 
					e[blk(i,j)].push_back(blk(i - 1,j));
					e[blk(i - 1,j)].push_back(blk(i,j));
				}
				if(j > 1 && c[i][j - 1] == 'O'){//向左建边 
					e[blk(i,j)].push_back(blk(i,j - 1));
					e[blk(i,j - 1)].push_back(blk(i,j));
				}
			}
		}
	}
	for(int i = 1; i <= n; i ++){
		for(int j = 1; j <= m; j ++){//匈牙利匹配,经测试只能找一个集合
			if(c[i][j] == 'O' || mat[blk(i,j)] == 0)
				continue;
			memset(vis,false,sizeof(bool) * (n * m + 1));
			H_srh(blk(i,j)); 
		}
	}
	scanf("%d",&k);
	if(mat[blk(x,y)] == 0){
		lf = false;
	}
	else{
		del = blk(x,y);
		mat[mat[blk(x,y)]] = 0;
		memset(vis,false,sizeof(bool) * (n * m + 1));
		if(H_srh(mat[blk(x,y)])){
			lf = false;
			mat[blk(x,y)] = 0;//去匹配 
		}
		else{
			lf = true;
			mat[mat[blk(x,y)]] = blk(x,y);
		}
	}
	for(int i = 1; i <= 2 * k; i ++){
		scanf("%d %d",&x,&y);
		if((i & 1) == 0)
			f1();
		else{
			f0();
			if(lf && nf){
				f.push_back((i + 1) >> 1);
			}
		}
	}
	printf("%u\n",f.size());
	for(unsigned i = 0; i < f.size(); i ++){
		printf("%d\n",f[i]);
	}
	return 0;
}
2024/1/3 20:34
加载中...