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

形式化题意

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

Solution

将总通信次数均摊到每个节点，得到58000=29×2000=(2×⌈log⁡2500⌉+⌈log⁡22000⌉)×200058000=29\times2000=(2\times\lceil \log_2500\rceil+\lceil \log_22000\rceil)\times 200058000=29×2000=(2×⌈log2​500⌉+⌈log2​2000⌉)×2000。

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

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

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

Code

Azer.cpp

#include"Azer.h"#include<vector>#definerep(i,a,b)for(inti(a);i<b;++i)#definerept(i,a,b)for(inti(a);i<=b;++i)#defineebemplace_backusingnamespacestd;namespace{constexprintMAXN=2005,INF=1e9;intN,u,t,lst,d[MAXN];boolf[MAXN],mk;vector<pair<int,int>>g[MAXN];vector<bool>buf;}voidFindA(){u=-1;rep(i,0,N)if(!f[i]&&(u==-1||d[i]<d[u]))u=i;if(u==-1)return;t=d[u];rep(i,0,9)SendA((d[u]==INF?511:d[u]-lst)>>i&1);// 注意特判d[u]=INF的情况}voidUpdA(){lst=d[u]=t,f[u]=true;for(auto[v,w]:g[u])d[v]=min(d[v],d[u]+w);}voidReceiveA(boolb){buf.eb(b);if(!mk&&buf.size()==9){intx=0;rep(i,0,9)x|=buf[i]<<i;buf.clear();x==511?x=INF:x+=lst;if(t<=x){// 白点来自Arep(i,0,11)SendA(u>>i&1);UpdA(),FindA();}elset=x,mk=true;}if(mk&&buf.size()==11){mk=false,u=0;rep(i,0,11)u|=buf[i]<<i;buf.clear();UpdA(),FindA();}}voidInitA(int_N,intA,vector<int>U,vector<int>V,vector<int>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<int>Answer(){returnvector<int>(d,d+N);}

Baijan.cpp

#include"Baijan.h"#include<vector>#definerep(i,a,b)for(inti(a);i<b;++i)#definerept(i,a,b)for(inti(a);i<=b;++i)#defineebemplace_backusingnamespacestd;namespace{constexprintMAXN=2005,INF=1e9;intN,u,t,lst,d[MAXN];boolf[MAXN],mk;vector<pair<int,int>>g[MAXN];vector<bool>buf;}voidFindB(){u=-1;rep(i,0,N)if(!f[i]&&(u==-1||d[i]<d[u]))u=i;if(u==-1)return;t=d[u];rep(i,0,9)SendB((d[u]==INF?511:d[u]-lst)>>i&1);}voidUpdB(){lst=d[u]=t,f[u]=true;for(auto[v,w]:g[u])d[v]=min(d[v],d[u]+w);}voidReceiveB(boolb){buf.eb(b);if(!mk&&buf.size()==9){intx=0;rep(i,0,9)x|=buf[i]<<i;buf.clear();x==511?x=INF:x+=lst;if(t<x){// 白点来自Brep(i,0,11)SendB(u>>i&1);UpdB(),FindB();}elset=x,mk=true;}if(mk&&buf.size()==11){mk=false,u=0;rep(i,0,11)u|=buf[i]<<i;buf.clear();UpdB(),FindB();}}voidInitB(int_N,intB,vector<int>U,vector<int>V,vector<int>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();}