题解 P5663 【加工零件】
Capitalism_Gao
2019-12-04 13:52:27
##### 前言：这篇文章只讲暴力，没有SPFA，没有图论！！！
## 关于搜索，它没有死！这题搜索可以拿到80pts！
#### 一般，考场上写暴力的话能写出40pts的代码，只有前8个点
#### 经过一些记忆化处理，可以骗到60pts
### 再经过一些对memset毒瘤处理，可以再骗走20pts
### 总体思路：牺牲空间换取时间
### 一.记忆化搜索60pts
用rec[u][l]表示工人u加工l阶段是否需要编号为1的人提供原料
需要：rec[u][l]=1;不需要rec[u][l]=-1;不确定：rec[u][l]=0;
观察数据可知本题询问q较大，所以每次完成一次询问后，就记录一次rec[u][l]
[测评结果](https://www.luogu.com.cn/record/28024466)
#### 参考代码：
```cpp
#include<bits/stdc++.h>
#define r register
using namespace std;
int read(){
int res=0,f=1;char ch;
while(isspace(ch=getchar()));
if(ch=='-') f=-1,ch=getchar();
do{
res=res*10+ch-'0';
}while(isdigit(ch=getchar()));
return res*f;
}
const int maxn=5555;
int cnt,head[maxn],n,m,q,rec[maxn][maxn],sure;
bool used[maxn];
struct edge{
int u,v,next;
}e[maxn];
inline void adde(int x,int y){
e[++cnt].u=x;
e[cnt].v=y;
e[cnt].next=head[x];
head[x]=cnt;
}
void dfs(int now,int depth){
if(sure==1) return;
if(rec[now][depth]==1){//需要worker1
sure=1;return;//打标记
}
if(rec[now][depth]==-1) return;//不需要返回即可
if(depth==1) {
for(r int i=head[now];i;i=e[i].next)
if(e[i].v==1){sure=1;break;}
if(sure!=1) rec[now][depth]=-1;
return;
}
for(r int i=head[now];i;i=e[i].next){//遍历每一条边
dfs(e[i].v,depth-1);
}
}
int main(){
n=read(),m=read(),q=read();
int u,v;
for(r int i=1;i<=m;i++){
u=read(),v=read();
adde(u,v);
adde(v,u);
}
int l;
for(r int k=1;k<=q;k++){
u=read(),l=read();
sure=-1;dfs(u,l);
if(sure==1) printf("Yes\n");
else printf("No\n");
rec[u][l]=sure;//记忆化
}
return 0;
}
```
### 二.算法改进80pts
不难发现：我们在搜索时会搜到很多相同的(u,l);
所以，我们在解决一个询问时，每当dfs(u,l)后就记录一个vis[u][l]=1;
**进入下一个询问时再将vis[][]清零即可。**
这样必定会节省很多时间。
**但是，问题来了：由于题中有很多个询问，怎样高效的清零呢？**
有大佬说：memset不就行了
很不幸的是，[测评结果](https://www.luogu.com.cn/record/28024849)将
会出人意料
TLE飞了
但是发现原来TLE的10#，11#，12#现在AC了；
原来AC的13#，14#，16#现在TLE了，并且每一个点的时间大幅增大
**不对啊,优化后效率反而更低，这是为什么呢**
其实，原因就在**memset**上
~~~cpp
memset(vis,0,sizeof(vis));
~~~
由于vis是个n*n的二维数组，n又很大，所以每次清零耗费了相当多的时间
**所以：改成循环呢？**
更是只有45pts
**难道就没有任何办法吗？？？**
**有！！！**
我们想办法让清零次数最少，那每次就只把改成1的赋值为0
(由于是bool数组，把1改成0，可以用取反"!"，常数优化)
我们执行vis[i][j]=1;后，**把i和j都用数组存下来**
就像这样
```cpp
for(r int i=head[now];i;i=e[i].next){
dfs(e[i].v,depth-1);
vis[e[i].v][depth-1]=1;
++cntmt;
xfkmt[cntmt]=e[i].v;
yfkmt[cntmt]=depth-1;
}
```
这样，我们在清零时直接：
```cpp
for(r int i=1;i<=cntmt;i++)
vis[xfkmt[i]][yfkmt[i]]=!vis[xfkmt[i]][yfkmt[i]];
```
**也就是：只清零有改动的数**
然后，818MS轻松AC前16个点！最后4个二维数组根本没法存！
[测评结果](https://www.luogu.com.cn/record/28055215)
### 三.参考程序
```cpp
#include<bits/stdc++.h>
#define r register
using namespace std;
int read(){
int res=0,f=1;char ch;
while(isspace(ch=getchar()));
if(ch=='-') f=-1,ch=getchar();
do{
res=res*10+ch-'0';
}while(isdigit(ch=getchar()));
return res*f;
}
const int maxn=2e4;
int cnt,n,m,q,sure,cntmt;
int head[maxn],rec[maxn][maxn],xfkmt[maxn],yfkmt[maxn];
bool vis[maxn][maxn];
struct edge{
int u,v,next;
}e[maxn];
inline void adde(int x,int y){
e[++cnt].u=x;
e[cnt].v=y;
e[cnt].next=head[x];
head[x]=cnt;
}
void dfs(int now,int depth){
if(sure==1) return;
if(rec[now][depth]==-1||vis[now][depth]) return;
if(rec[now][depth]==1){
sure=1;return;
}
if(depth==1) {
for(r int i=head[now];i;i=e[i].next)
if(e[i].v==1){sure=1;break;}
if(sure!=1) rec[now][depth]=-1;
return;
}
for(r int i=head[now];i;i=e[i].next){
dfs(e[i].v,depth-1);
vis[e[i].v][depth-1]=1;
++cntmt;
xfkmt[cntmt]=e[i].v;
yfkmt[cntmt]=depth-1;
}
}
int main(){
n=read(),m=read(),q=read();
int u,v;
for(r int i=1;i<=m;i++){
u=read(),v=read();
adde(u,v);
adde(v,u);
}
int l;
for(r int k=1;k<=q;k++){
u=read(),l=read();
cntmt=0;sure=-1;
dfs(u,l);
if(sure==1) printf("Yes\n");
else printf("No\n");
rec[u][l]=sure;
for(r int i=1;i<=cntmt;i++)
vis[xfkmt[i]][yfkmt[i]]=!vis[xfkmt[i]][yfkmt[i]];
}
return 0;
}
```