题解 P5663 【加工零件】

· · 题解

前言：这篇文章只讲暴力，没有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]
测评结果

参考代码：

#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不就行了
很不幸的是，测评结果将 会出人意料
TLE飞了
但是发现原来TLE的10#，11#，12#现在AC了；
原来AC的13#，14#，16#现在TLE了，并且每一个点的时间大幅增大

不对啊,优化后效率反而更低，这是为什么呢
其实，原因就在memset上

memset(vis,0,sizeof(vis));

由于vis是个n*n的二维数组，n又很大，所以每次清零耗费了相当多的时间

所以：改成循环呢？
更是只有45pts

难道就没有任何办法吗？？？
有！！！
我们想办法让清零次数最少，那每次就只把改成1的赋值为0
(由于是bool数组，把1改成0，可以用取反"!"，常数优化)

我们执行vis[i][j]=1;后，把i和j都用数组存下来
就像这样

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;
}

这样，我们在清零时直接：

for(r int i=1;i<=cntmt;i++)
    vis[xfkmt[i]][yfkmt[i]]=!vis[xfkmt[i]][yfkmt[i]];

也就是：只清零有改动的数

然后，818MS轻松AC前16个点！最后4个二维数组根本没法存！

测评结果

三.参考程序

#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;
}