题解：P11564 【MX-X7-T5】[LSOT-3] 你的列车是生存战略

· · 题解

这道题不放图片有点太难以理解了（至少对于我来说）。

思路

首先，\Theta(n^2) 的建图方式应该都会吧。

有一个 Trick，每次反转编号二进制的一位，然后建图，这道题就用上了。

然后看到或运算和与运算，以及 a,b 的单调性，想到，或运算只会不变和变大，与运算只会不变和减小，所以我们只需要反转一位就行了，具体按以下方式考虑：

或运算：

将每一个 c_i（c_i 不局限于出现过的掩码，是所有 [0,2^k) 范围内的掩码），枚举二进制位，如果为 0，则反转这一位成 1，设得到新数位 s，表示一个中转点。

以便于处理边权，我们设 ina(s) 表示从正常图进入中转点 s 的编号，outa(s) 表示出中转点 s 回到正常图的编号。

然后建三条单向边 c_i\to ina(s)\to outa(s)\to c_j。c_j 是 s 将 1 位反转后所产生的值，其中 ina(s)\to outs(s) 这条边，边权即为 a_s，若正好为 c_i|c_j 的值则最好，如果现在 s\ne c_i|c_j，则必定有一条边满足 a_{s_0}\le a_s，且有 s_0=c_i|c_j（因为 a 满足单调性）。

不懂的看图：

左右两侧的点为 ina 和 outa 的点，真正的实点还在两侧连接 ina 和 outa 的点。

与运算

与或运算的区别是，如果是 1 位则反转成 0。

并变成 d 数组和 inb(s),outb(s)。

图也是如此，并将这两种运算放在同一个图里就行了，最短路会自动选择更优的路径。

时间复杂度 \Theta((x+m+k\times 2^k)\times \log(n+2^k))。

代码

代码使用 AI 润色。

代码中的内容如有不懂的，可以根据上面的图一起看。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=4e18;
const int MAXN=1070000, MAXE=6100000;
int n,m,k,M,tot;
int head[MAXN],to[MAXE],nxt[MAXE],c[MAXN],d[MAXN];
ll ew[MAXE],dis[MAXN],A[16385],B[16385];

inline void add(int u,int v,ll w){
    to[++tot]=v;ew[tot]=w;nxt[tot]=head[u];head[u]=tot;
}
inline int read(){
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}
inline ll readll(){
    ll x=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}
inline int ina(int s){return n+1+s;}
inline int outa(int s){return n+M+1+s;}
inline int inb(int s){return n+2*M+1+s;}
inline int outb(int s){return n+3*M+1+s;}

int main(){
    n=read();m=read();k=read();M=1<<k;
    for(int i=1;i<=n;i++) c[i]=read();
    for(int i=1;i<=n;i++) d[i]=read();
    for(int s=0;s<M;s++) A[s]=readll();
    for(int s=0;s<M;s++) B[s]=readll();
    for(int i=1;i<=n;i++){
        add(i,ina(c[i]),0);
        add(outa(c[i]),i,0);
        add(i,inb(d[i]),0);
        add(outb(d[i]),i,0);
    }
    for(int s=0;s<M;s++){
        add(ina(s),outa(s),A[s]);
        add(inb(s),outb(s),B[s]);
        for(int p=0;p<k;p++){
            int b=1<<p;
            if(!(s&b)){
                add(ina(s),ina(s|b),0);
                add(outb(s),outb(s|b),0);
            }else{
                add(outa(s),outa(s^b),0);
                add(inb(s),inb(s^b),0);
            }
        }
    }
    for(int i=1;i<=m;i++){
        int u=read(),v=read();
        add(u,v,readll());
    }
    int N=n+4*M;
    for(int i=1;i<=N;i++) dis[i]=INF;
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> q;
    dis[1]=0;q.push(make_pair(0,1));
    while(!q.empty()){
        pair<ll,int> cur=q.top();q.pop();
        ll du=cur.first;int u=cur.second;
        if(du!=dis[u]) continue;
        for(int e=head[u];e;e=nxt[e]){
            int v=to[e];
            if(dis[v]>du+ew[e]){
                dis[v]=du+ew[e];
                q.push(make_pair(dis[v],v));
            }
        }
    }
    for(int i=1;i<=n;i++) printf("%lld ",dis[i]);
    return 0;
}
完结撒花。