通信题,Alice 和 Bob 会收到同一个 个点 条边的无向图,Alice 会额外收到这个图的一个合法 染色。Alice 要向 Bob 发一个长度小于等于 的 串,Bob 需要根据这个 串还原出任意一个合法的 染色方案。
,。
考虑让 Alice 发送每个点颜色 的结果,然后 Bob 就可以通过对同色子图进行二分图染色来还原方案。
这样需要发送长 的 串,考虑剪枝,不难发现度数 的点不用发,那么需要发的长度降到了 ,可以通过本题。
代码如下:
Alice.cpp:
#include "Alice.h"
const int S=200005;
std::vector<int> Alice(int N,int M,std::vector<int> U,std::vector<int> V,std::vector<int> C)
{
std::vector<int> res;
std::vector<std::vector<int>> g;
for(int i=0;i<N;i++) g.push_back(std::vector<int>());
for(int i=0;i<M;i++) g[U[i]].push_back(V[i]),g[V[i]].push_back(U[i]);
for(int i=0;i<N;i++)
{
if(g[i].size()>=8)
{
int idx=C[i]&3;
res.push_back(idx>>1&1);
res.push_back(idx&1);
}
}
return res;
}
Bob.cpp:
#include "Bob.h"
#include <cstdio>
#include <queue>
std::vector<int> Bob(int N,int M,std::vector<int> U,std::vector<int> V,std::vector<int> X)
{
std::vector<int> res,flg;
std::vector<std::vector<int>> g;
for(int i=0;i<N;i++) g.push_back(std::vector<int>()),flg.push_back(-1);
for(int i=0;i<N;i++) res.push_back(-1);
for(int i=0;i<M;i++) g[U[i]].push_back(V[i]),g[V[i]].push_back(U[i]);
std::vector<std::pair<int,int>> val;
for(int i=0,j=0;i<N;i++)
{
if(g[i].size()>=8)
{
int idx=0;
idx=idx<<1|X[j++];
idx=idx<<1|X[j++];
flg[i]=idx;
val.push_back(std::make_pair(i,idx));
}
}
for(int id=0;id<=3;id++)
{
for(std::pair<int,int> u:val)
{
if(u.second==id&&res[u.first]==-1)
{
std::queue<int> q;
q.push(u.first);
res[u.first]=id;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int v:g[u])
{
if(flg[v]==id&&res[v]==-1)
{
res[v]=res[u]==id?4+id:id;
q.push(v);
}
}
}
}
}
}
for(int i=0;i<N;i++)
{
if(g[i].size()<8)
{
bool vis[8];
for(int j=0;j<8;j++) vis[j]=false;
for(int v:g[i]) if(res[v]!=-1) vis[res[v]]=true;
for(int j=0;j<8;j++) if(!vis[j]) res[i]=j;
}
}
return res;
}