题解：P14371 [JOISC 2018] 航空路线图 / Airline Route Map

· · 题解

通信。

Description

通信题。

Alice 会得到一张无向简单图 G，然后 Alice 需要构造一张新的无向简单图 G'。

将这张图的点和边的顺序全部打乱之后的 G'' 再传递给 Bob，Bob 需要根据 G'' 还原出 G。

设 G 的点数为 N，边数为 M，1\le N\le 1000，0\le M\le \frac{N(N-1)}{2}，点的编号从 0 开始。

设 Alice 构造的图 G' 的点数为 N'，边数为 M'，你需要保证 1\le N'\le N+12，0\le M'\le \frac{N'(N'-1)}{2}。

Solution

首先因为你要把 G 传过去，所以你肯定得把 G 塞进 G' 里，但你发现因为点和边会被打乱，所以 Bob 是无法区分这些点原本是谁的。

但你发现你多出来了 12 个点，好好考虑一下怎么用。

注意到 2^{10}=1024>1000，考虑拿出来 10 个点，分别代表 2^0,2^1,\ldots,2^9。对每个 0<i<N 二进制分解，对于其拥有的 2^k，将 G' 上编号为 i 的点连接到代表 2^k 的点上。

因为这 10 个点是有顺序的，所以我们将这 10 个点从 2^0 到 2^9 连成一条链。

现在虽然有了标记点的方法，可是我们仍然无法从 G'' 区分出来这些点。

从剩下的 2 个点里挑一个出来，只连 10 条边，分别连接到 2^0 到 2^9 上。这样我们只需要区分出这个链标记点，并确定链的起点在哪就行了。

此时我们没有别的可以利用的信息了，考虑从点的度数下手。

最后 1 个点，我们连接除了那个链标记点的其他所有点，这个点的度数为 N+10，不难发现这是一定能区分出来的。

如何给链定向？不难发现，对于 0\sim 999 而言，包含了 2^9 的数的数量肯定小于包含 2^0 的数的数量。

所以度数较大的那个就是链头，较小的是链尾。

然后就可以对原图上的点还原其编号了，G 自然就还原出来了。

Code

:::success[代码]

#include<vector>
using namespace std;

#include "Alicelib.h"
// ------ Alicelib.h -----------------------------
// void Alice( int N, int M, int A[], int B[] );
// void InitG( int V, int U );
// void MakeG( int pos, int C, int D );
// -----------------------------------------------

void Alice(int N,int M,int A[],int B[]){
    vector<pair<int,int> > G;

    for(int i=0;i<M;i++) G.push_back({A[i],B[i]});
    for(int i=0;i<N;i++) for(int p=0;p<10;p++) if(i&(1<<p)) G.push_back({i,N+p});
    for(int i=0;i<N+10;i++) G.push_back({i,N+10});
    for(int i=N;i<N+9;i++) G.push_back({i,i+1});
    for(int i=N;i<N+10;i++) G.push_back({i,N+11});

    InitG(N+12,(int)G.size());
    for(int i=0;i<(int)G.size();i++) MakeG(i,G[i].first,G[i].second);
}
#include<vector>
using namespace std;

#include "Boblib.h"
// ------ Boblib.h --------------------------
// void Bob( int V, int U, int C[], int D[] );
// void InitMap( int N, int M );
// void MakeMap( int A, int B );
// ------------------------------------------

void Bob(int V,int U,int C[],int D[]){
    vector<int> deg(V,0),g[1012];
    for(int i=0;i<U;i++){
        g[C[i]].push_back(D[i]),g[D[i]].push_back(C[i]);
        deg[C[i]]++,deg[D[i]]++;
    }

    int flagpos=0;
    for(int i=0;i<V;i++) if(deg[i]>deg[flagpos]) flagpos=i;

    vector<int> vis(V,1);vis[flagpos]=0;
    for(int y:g[flagpos]) vis[y]=0;

    int chainflag=-1;
    for(int i=0;i<V;i++) if(vis[i]) chainflag=i,vis[i]=0;
    for(int y:g[chainflag]) vis[y]=1;

    vector<int> ddeg(V,0);
    for(int i=0;i<U;i++) if(vis[C[i]]&&vis[D[i]]) ddeg[C[i]]++,ddeg[D[i]]++;

    int chainbegin=-1;
    for(int i=0;i<V;i++) if(vis[i]&&ddeg[i]==1&&(chainbegin==-1||deg[i]>deg[chainbegin])) chainbegin=i;

    vector<int> vvalue(V,0);
    vvalue[chainbegin]=1;

    int nowpos=chainbegin,cnt=2;
    while(true){
        bool brk=true;
        for(int y:g[nowpos]) if(vis[y]&&!vvalue[y]){
            vvalue[y]=cnt,cnt<<=1,brk=false,nowpos=y;
            break;
        }
        if(brk) break;
    }

    vector<int> org(V,0);
    for(int i=0;i<V;i++){
        if(i==flagpos||i==chainflag||vis[i]) continue;
        for(int y:g[i]) org[i]+=vvalue[y];
    }

    vector<pair<int,int> > G;
    for(int i=0;i<U;i++){
        if(C[i]==flagpos||C[i]==chainflag||vis[C[i]]) continue;
        if(D[i]==flagpos||D[i]==chainflag||vis[D[i]]) continue;
        G.push_back({org[C[i]],org[D[i]]});
    }

    InitMap(V-12,(int)G.size());
    for(auto [x,y]:G) MakeMap(x,y);
}

:::