题解 P8117 【「Wdoi-1.5」旅人 1977】

囧仙 · 2022-02-09 19:33:44 · 题解

题解

\textbf{Subtask 1}

容易发现一条边走多次总是不优的。因此可以直接暴力 \text{dfs}。

\textbf{Subtask 2}

用来给选手确认一下题意是否理解正确，因此设置了这个相当于是骗分的点。

\textbf{Subtask 3 \& 4}

开始进入正题。考虑一条边究竟会对最终的结果产生多大的贡献。容易发现，一条边产生的贡献会受到这条边之后的边对 \text{tag} 的更新的影响。因此正着推是非常困难的（无法消除后效性）。不妨反过来想，只要知道了从一个点到达终点到底有哪些位置被更新了 \text{tag}，就可以很好地计算出 w_i 产生的贡献的次数。

于是可以把所有的边反过来然后 \text{dp}，对于点 i 记录一个状态 u，表示从它到达终点会有哪些节点会被产生更新。更新过程有这样一个特点：每次更新是自上而下的，下边某个节点的向下更新肯定是在它父亲节点向下更新之后。同时还有一个特点，每当一个带有 \text{tag} 的节点向下更新后，带有这个 \text{tag} 的节点个数恰好会增加 1 个。但是会有一些实现细节上的问题，这也就区分了这两个 \text{Subtask}。

值得注意的是，所有的叶子节点是不会被更新的，因此维护的状态不需要存储最底下这一层，下文把非叶节点称作有效节点。也就是下图当中红色的部分。

首先使用 \text{dfs} 对有效节点进行编号。记有效节点个数为 s，那么 s 大约是 k 左右。可以发现有效节点可以进行状压，放到一个 \text{unsigned} 里边。对于这两个 \text{Subtask}，图上是一个 \text{DAG}，因此可以按照拓扑排序的顺序进行处理。对于每条边 (u_i,v_i,l_i,r_i,w_i)，考虑枚举 v_i 的状态（设枚举的状态为 y），由此更新出 u_i 对应状态的结果（设为 x）。那么我们需要计算这两个东西：

其中 A_{l,r} 和 B_{l,r} 都是状态压缩后的状态。由于 1\le l_i\le r_i\le k，因此可以直接 k^3 暴力预处理出这三个东西。放一个例子：

这张图展现了 (2,6) 这样一条边的情况。我们应该预处理出被标成浅蓝色的这些节点所组成的状态为 A_{l,r}，深蓝色的节点组成的状态为 B_{l,r}。同时还需要计算出这条边实际给多少个节点打上了 \text{tag}，这个例子当中是 2（[2,5) 和 [5,7)）。要注意，统计 \mathit{num}_{l,r} 时不能忽略叶子节点被打上 \text{tag} 的情况（这个例子里没有出现这样的情况而已）。

$$\mathit{dp}_{u,y\operatorname{or} B_{l,r}}\gets\min\{\mathit{dp}_{u,y\operatorname{or} B_{l,r}},\mathit{dp}_{v,y}+w_i\cdot(\operatorname{popcount}(y\operatorname{and} A_{l,r})+\mathit{num}_{l,r})\}$$ 其中 $\operatorname{popcount}(x)$ 表示 $x$ 在二进制下 $1$ 的个数。一种快速的实现方法是，预处理出 $0\sim 255$ 中每个数字二进制下 $1$ 的个数记为 $\mathit{pop}_0(x)$，那么 $\operatorname{popcount}(x)$ 就等于把 $x$ 分成四部分（用位运算实现）分别取 $\mathit{pop}_0$ 数组得到结果相加。这样复杂度几乎可以认为是常数。当然也可以用一些内置函数。如果直接暴力枚举 $2^k$ 种状态，那么时间复杂度应当是 $\mathcal O(k^3+2^{k-1}\cdot m)$ 的，可以通过 $\text{Subtask 3}$。但可以发现一些状态是不可能实现的（诸如一个有效节点所对应的二进制值为 $1$，而它的父亲节点对应的二进制值却是 $0$）。我们称可以实现的状态为**有效状态**。考虑怎么计算长度为 $k$ 的线段树的有效状态总个数。设 $f(x)$ 为长度为 $x$ 对应的线段树的**非空的**有效状态数。容易发现， $$ f(x)=\begin{cases} 0 & x\le 1 \cr (f(\lfloor\frac{x}{2}\rfloor)+1)\cdot (f(\lceil\frac{x}{2}\rceil)+1) & x> 1 \end{cases} $$ 经过计算，可以得到 $f(\left.s\right|_{k=30})\approx 1.74\times 10^5$，这是远远小于 $2^{\left.s\right|_{k=30}}\approx 2.68\times 10^8$ 的。（$\left.s\right|_{k=30}=28$）下一步是如何枚举出所有有效状态。这一步并不太难。你可以仿照 $\text{dp}$ 计算有效状态数的方法递归地计算出所有状态，但是比较麻烦。这里提供另外一种简单粗暴的方案。直接用 $\text{dfs}$ **依次**枚举 $0\sim s-1$ 位应当是填充 $0$ 还是 $1$。**当某个节点的父亲节点为** $\bm 0$，**则该节点只能填** $\bm 0$。经过这样一个剪枝可以剪掉所有无用方案而恰好保留所有有效状态，复杂度是 $\mathcal O(f(s))$。总时间复杂度为 $\mathcal O(f(s)\cdot m)$，空间复杂度为 $\mathcal O(f(s)\cdot n)$。 ### $\textbf{Subtask 5 \& 6}

小清新 \text{Subtask}。可以发现瓶颈在于该子任务不再是有向无环图。

使用分层图，将每个点拆成 f(s) 个点，每个点对应于一个状态。按照刚刚 \text{dp} 的方式进行连边，总共连了 f(s)\cdot m 条边。如果你直接使用堆优化 \text{Dijsktra} 跑最短路，复杂度上会多一只 \log。但是可以发现本题答案不超过 n\cdot 2k\cdot \max\{w_i\}，估摸一下最大为 50\cdot 60\cdot 10^3=3\times 10^5，因此可以直接上桶排。复杂度降为 \mathcal O(f(s)\cdot m)。

总时间复杂度分析：

使用 \mathcal O(k) 的复杂度计算出所有有效节点的标号。
使用 \mathcal O(f(s)) 的复杂度计算出所有有效状态。
使用 \mathcal O(k^3) 暴力预处理出所有可能的 (l,r) 对应的 A,B,\mathit{num}。
建立分层图跑最短路，复杂度为 \mathcal O(f(s)\cdot m)。

然而如果你先连边再跑最短路，空间复杂度达到了惊人的 \mathcal O(f(s)\cdot m)，然后发现你只能过 \text{Subtask 5}。但是完全可以在计算最短路的同时进行边的生成，此时空间复杂度降到了 \mathcal O(n\cdot f(s))，可以通过本题。

参考代码

#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
typedef long long i64;
const int INF =2147483647;
typedef unsigned int       u32;
typedef unsigned long long u64;
namespace Hsh{
    const int SIZ =3e6-3;
    int H[SIZ],N[SIZ],W[SIZ],t; u32 V[SIZ];
    void add(int u,u32 v,int w){
        V[++t]=v,W[t]=w,N[t]=H[u],H[u]=t;
    }
    int get(u32 w){
        for(int i=H[w%SIZ];i;i=N[i]) if(V[i]==w) return W[i];
        return 0;
    }
}
namespace IIT{
    const int MAXN=16261+3,MAXS=32+3;
    int L[MAXS],R[MAXS],P[MAXS],Q[MAXS],F[MAXS],s,g;
    u32 A[MAXS][MAXS],B[MAXS][MAXS],N[MAXS][MAXS],C[MAXN];
    map<u32,int> M;
    int bld(int t,int l,int r){
        L[t]=l,R[t]=r; if(l!=r){
            int c=l+r>>1;
            if(l!=c  ) P[t]=bld(++s,l,c  ),F[P[t]]=t;
            if(r!=c+1) Q[t]=bld(++s,c+1,r),F[Q[t]]=t;
        }
        return t;
    }
    int T[MAXS],o;
    void clc(int t,int l,int r){
        if(l<=L[t]&&R[t]<=r){T[t]=-1,++o;} else {
            int c=L[t]+R[t]>>1; T[t]=1;
            if(l<=c&&P[t]) clc(P[t],l,r); else if(l<=c) ++o;
            if(r> c&&Q[t]) clc(Q[t],l,r); else if(r> c) ++o;
        }
    }
    void dfs(int x,u32 u,int k){
        if(x==s+1) {C[++g]=u,Hsh::add(u%Hsh::SIZ,u,g); return;}
        if(u&(1u<<F[x])) dfs(x+1,u|1u<<x,k);
        dfs(x+1,u,k);
    }
    void iit(int k){
        bld(0,1,k),dfs(1,1,k);
        up(1,k,i) up(i,k,j){
            memset(T,0,sizeof(T)),clc(0,i,j);
            N[i][j]=o,o=0; up(0,s,x){
                if(T[F[x]]==-1) T[x]=-1;
                if(T[x]==-1) A[i][j]|=1u<<x;
                if(T[x]== 1) B[i][j]|=1u<<x;
            }
        }
    }
}
namespace Lst{
    const int MAXN =4e6+3,SIZ =2e7+3;
    int H[MAXN],V[SIZ],N[SIZ],t;
    void add(int u,int v){
        V[++t]=v,N[t]=H[u],H[u]=t;
    }
}
namespace Gra{
    const int MAXN=1000+3,MAXM=3000+3;
    const int SIZ =16261+3;
    int H[MAXN],V[MAXM],T[MAXM],L[MAXM],R[MAXM],W[MAXM],s,t;
    void add(int u,int v,int l,int r,int w){
        V[++t]=v,L[t]=l,R[t]=r,W[t]=w,T[t]=H[u],H[u]=t;
    }
    const int MAXW=65536;
    int D[MAXN*SIZ],G[MAXW];
    int ppc(u32 u){
        return G[u>>16]+G[u&0xFFFF];
    }
    int dij(int a,int b){
        using IIT::g; using IIT::C; using IIT::A;
        using IIT::B; using IIT::M; using IIT::N;
        up(0,65535,i) G[i]=G[i>>1]+(i&1); Lst::add(1,b*(g+1));
        up(1,Lst::MAXN,d) for(int oo=Lst::H[d];oo;oo=Lst::N[oo]){
            int o=Lst::V[oo]; if(D[o]&&D[o]<d) continue; D[o]=d;
            int u=o/(g+1),x=o%(g+1); if(u==a) return d-1;
            for(int i=H[u];i;i=T[i]){
                int v=V[i],l=L[i],r=R[i],y=Hsh::get(C[x]|B[l][r]);
                int w=W[i]*(ppc(C[x]&A[l][r])+N[l][r]);
                int p=v*(g+1)+y;
                if(D[p]>d+w||!D[p]) Lst::add(d+w,p),D[p]=d+w;
            }
        }
        return -1;
    }
}
namespace Slv{
    const int MAXN=1000+3,MAXM=16261+3,MAXK=3000+3;
    int U[MAXK],V[MAXK],L[MAXK],R[MAXK],K[MAXK];
    int qread(){
        int w=1,c,ret;
        while((c=getchar())> '9'||c< '0') w=(c=='-'?-1:1); ret=c-'0';
        while((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0';
        return ret*w;
    }
    int n,m,k,a,b,t,ans=1e9;
    void mian(){
        n=qread(),m=qread(),k=qread(),a=qread(),b=qread(); IIT::iit(k);
        up(1,m,i){
            int u=qread(),v=qread(),l=qread(),r=qread(),w=qread();
            Gra::add(v,u,l,r,w);
        }
        printf("%d\n",Gra::dij(a,b));
    }
}
int main(){
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    Slv::mian(); return 0;
}