题解：P9377 [THUPC 2023 决赛] 百合

· · 题解

传送门

思路

直接建图显然不行。

这种建完全图的题有一个很典的 trick：建虚点（辅助点）或拆点。

又发现 x 和 y 的不同二进制位数 k 很难维护，因此不妨把它改为：将 x 取反 k 位后的值。

发现这个东西仍然很难维护，又因为位数很少，不妨按位决策。

设点 (x,i,j) 为前 i 位，取反了 j 个位置的值是 x。

建边是显然的。

因为原图中本来就有的边可以互相抵达，所以若 x 与 y 有一条边权为 w 的边，建边 (x,0,0) 到 (y,0,0)，边权为 w。

对于点 (x,i,j)，它的第 i+1 位可以不取反，则建边 (x,i,j) 到 (x,i+1,j)，边权为 0。注意边界 i<k。

对于点 (x,i,j)，它的第 i+1 位可以取反，则建边 (x,i,j) 到 (x\oplus2^i,i+1,j+1)，边权为 0。注意边界 i<k。

对于点 (x,0,0)，它可以花费 a_j 抵达任意符合边界条件的 (x,i,j)，因此建边 (x,0,0) 到 (x,i,j)，边权为 a_j。

代码中并不需要把这些边建出来。

发现时间复杂度是 O((m+2^kk^2) \log 2^kk^2) 的，无法接受。

发现图中有很多边权为 0 的边，因此松弛这些边的时候并不需要维护优先队列，单独跑一遍就行。

最终的时间复杂度为 O((m+2^kk) \log 2^kk^2)，可以通过。

代码

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int k,m,s;
int a[18],dis[150005];
bool vis[150005],vis2[150005][20][20];
struct node{
    int x,w;
    bool operator < (const node &b) const{
        return b.w<w;
    }
};
struct node2{
    int x,y,z;
};
vector<node> v[150005];
priority_queue<node> que;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> k >> m >> s;
    for(int i=1;i<=k;i++){
        cin >> a[i];
    }
    for(int i=1;i<=m;i++){
        int x,y,w;
        cin >> x >> y >> w;
        v[x].push_back((node){y,w});
        v[y].push_back((node){x,w});
    }
    memset(dis,0x3f,sizeof(dis));
    dis[s] = 0;
    que.push((node){s,0});
    while(!que.empty()){
        node t = que.top();
        que.pop();
        if(vis[t.x]){
            continue;
        }
        vis[t.x] = 1;
        for(auto x:v[t.x]){
            if(dis[x.x]>dis[t.x]+x.w){
                dis[x.x] = dis[t.x]+x.w;
                que.push((node){x.x,dis[x.x]});
            }
        }
        queue<node2> q;
        q.push((node2){t.x,0,0});
        while(!q.empty()){
            node2 t2 = q.front();
            q.pop();
            vis2[t2.x][t2.y][t2.z] = 1;
            if(k==t2.y){
                if(dis[t2.x]>dis[t.x]+a[t2.z]){
                    dis[t2.x] = dis[t.x]+a[t2.z];
                    que.push((node){t2.x,dis[t2.x]});
                }
            }
            else if(t2.y<k){
                if(!vis2[t2.x][t2.y+1][t2.z]){
                    q.push((node2){t2.x,t2.y+1,t2.z});
                }
                if(!vis2[t2.x^(1<<t2.y)][t2.y+1][t2.z+1]){
                    q.push((node2){t2.x^(1<<t2.y),t2.y+1,t2.z+1});
                }
            }
        }
    }
    for(int i=0;i<(1<<k);i++){
        cout << dis[i] << " ";
    }
    return 0;
}