洛谷-P14345 [JOISC 2019] Two Transportations 题解

形式化题意

给定一张 \(N\) 个节点 \(A+B\) 条边的无向连通图，边权是 \(\le 500\) 的正整数。Azer 知道其中 \(A\) 条边，Baijan 知道另外 \(B\) 条。双方最多可以互相发送 \(58000\) 比特信息，需要共同求从 \(0\) 到所有节点的最短路。

Solution

将总通信次数均摊到每个节点，得到 \(58000=29\times2000=(2\times\lceil \log_2500\rceil+\lceil \log_22000\rceil)\times 2000\)。

\(N\) 很小，而图很稠密，我们可以考虑 \(O(n^2)\) 的朴素 Dijkstra。每次找当前蓝点中距离最小的点，把它标记为白点，并松弛它的所有出边。

每一轮中，两人只需分别找出本地距离最小的蓝点，通过通信得出全局距离最小的蓝点，然后分别在本地用该点进行松弛即可。

因为边权 \(\le500\)，所以每一轮新白点的最短路与上一个白点最短路之差一定 \(\le 500\)。双方互相发送距离增量只需 \(2 \times 9\) 比特。然后距离较小的人需要向另一人发送该点编号，需要 \(11\) 比特。恰好满足限制。

Code

Azer.cpp

#include "Azer.h"
#include 
#define rep(i,a,b) for(int i(a);i> g[MAXN];
    vector buf;
}
void FindA(){
    u=-1;
    rep(i,0,N) if(!f[i]&&(u==-1||d[i]>i&1);  // 注意特判d[u]=INF的情况
}
void UpdA(){
    lst=d[u]=t,f[u]=true;
    for(auto [v,w]:g[u]) d[v]=min(d[v],d[u]+w);
}
void ReceiveA(bool b){
    buf.eb(b);
    if(!mk&&buf.size()==9){
        int x=0;
        rep(i,0,9) x|=buf[i]<>i&1);
            UpdA(),FindA();
        }else t=x,mk=true;
    }
    if(mk&&buf.size()==11){
        mk=false,u=0;
        rep(i,0,11) u|=buf[i]< U,vector V,vector C){
    N=_N;
    fill(d+1,d+N,INF);
    rep(i,0,A){
        g[U[i]].eb(V[i],C[i]);
        g[V[i]].eb(U[i],C[i]);
    }
    FindA();
}
vector Answer(){
    return vector(d,d+N);
}

Baijan.cpp

#include "Baijan.h"
#include 
#define rep(i,a,b) for(int i(a);i> g[MAXN];
    vector buf;
}
void FindB(){
    u=-1;
    rep(i,0,N) if(!f[i]&&(u==-1||d[i]>i&1);
}
void UpdB(){
    lst=d[u]=t,f[u]=true;
    for(auto [v,w]:g[u]) d[v]=min(d[v],d[u]+w);
}
void ReceiveB(bool b){
    buf.eb(b);
    if(!mk&&buf.size()==9){
        int x=0;
        rep(i,0,9) x|=buf[i]<>i&1);
            UpdB(),FindB();
        }else t=x,mk=true;
    }
    if(mk&&buf.size()==11){
        mk=false,u=0;
        rep(i,0,11) u|=buf[i]< U,vector V,vector C){
    N=_N;
    fill(d+1,d+N,INF);
    rep(i,0,B){
        g[U[i]].eb(V[i],C[i]);
        g[V[i]].eb(U[i],C[i]);
    }
    FindB();
}