错失AK良机的测试48T3 Walk

图论一般技巧新建虚点。

新建2^k个虚点。

四种转移。普通点n，新点k。

n->n 1

n->k(自己的) 0

k->k 0

k->n 1

本题bfs,边权为1，则最先扫到最优，要避免重复扫。

使虚点只用来更新一次，只入队一次，从而避免重复考虑。

枚举子集：见小技巧标签的博客。

对于每个点枚举子集，(2^k)^2;

但是要是每个点只扫一次。

发现子集如果扫过，子集的子集一定扫过。

所以每次只考虑下一层子集，放到队列里即可。

O(n+m+2^k)

#include<bits/stdc++.h>
#define F(i,a,b) for(rg int i=a;i<=b;++i)
#define LL long long
#define rg register
#define il inline
#define pf(a) printf("%d ",a)
#define phn puts("")
using namespace std;
int read();
/*
单向双向
*/
#define N 300010
#define M 1000010
#define ID 2000010
int n,m,K,val[N],ok[ID];
int to[M],fir[M],head[ID],cnt;
il void add(int x,int y){to[++cnt]=y;fir[cnt]=head[x];head[x]=cnt;}
int dis[ID],vis[ID],id[1500010],gx[ID];
deque<int>q;
il int max(int x,int y){return x>y?x:y;}
#define inp(x) q.push_front(x)
#define inb(x) q.push_back(x)
#define out() q.pop_front()
int main(){
    n=read();m=read();
    F(i,1,n)val[i]=read(),K=max(K,val[i]),ok[val[i]]=1;
    F(i,0,K)id[i]=n+i+1;
    F(i,1,n){
        add(id[val[i]],i);
    }
    rg int u,v,x;
    F(i,1,m){
        u=read();v=read();add(u,v);
    }
    memset(dis,-1,sizeof(dis));
    inb(1);vis[1]=1;dis[1]=0;
    while(!q.empty()){
        u=q.front();out();
    //    pf(u);
        if(u<=n){
            for(rg int i=head[u];i;i=fir[i]){
                if(!vis[v=to[i]]){
                    vis[v]=1;dis[v]=dis[u]+1;inb(v);
                }
            }
            if(!vis[id[x=val[u]]]){
                vis[id[x]]=1;dis[id[x]]=dis[u];
            }
            if(!gx[x]){
                gx[x]=1;
                for(rg int i=head[id[x]];i;i=fir[i]){
                    if(!vis[v=to[i]]){
                        vis[v]=1;dis[v]=dis[u]+1;inb(v);
                    }
                }
                for(rg int j=x;j;j-=j&-j){
                    if(!vis[v=id[x-(j&-j)]]){
                    vis[v]=1;dis[v]=dis[u];inp(v);
                    }
                }
            }
        }
        else{
            x=u-n-1;
            if(!gx[x]){
                gx[x]=1;
                for(rg int i=head[u];i;i=fir[i]){
                    if(!vis[v=to[i]]){
                        vis[v]=1;dis[v]=dis[u]+1;inb(v);
                    }
                }
                for(rg int j=x;j;j-=j&-j){
                    if(!vis[v=id[x-(j&-j)]]){
                    vis[v]=1;dis[v]=dis[u];inp(v);
                    }
                }
            }
        }
    }
    F(i,1,n)printf("%d\n",dis[i]);
}
il int read(){
    int s=0;char ch;
    while(ch=getchar(),!isdigit(ch));
    for(;isdigit(ch);s=s*10+(ch^48),ch=getchar());
    return s;
}
/*
g++ 1.cpp -g
./a.out
5 2
5 4 2 3 7
1 4
2 3
*/

View Code

技巧总结：

树、图：边化点，点化边，互化。

图：建立虚点、拆点、源点汇点。

图到树：最小生成树。

树链：1、树剖 2、倍增 (最终询问可倍增下放)