POJ21677 / QOJ141 染色 做题记录

通信题,Alice 和 Bob 会收到同一个 nn 个点 mm 条边的无向图,Alice 会额外收到这个图的一个合法 88 染色。Alice 要向 Bob 发一个长度小于等于 2.5×1052.5\times 10^50101 串,Bob 需要根据这个 0101 串还原出任意一个合法的 88 染色方案。

1n2×1051\le n\le 2\times 10^51m5×1051\le m\le 5\times 10^5

考虑让 Alice 发送每个点颜色 mod4\operatorname{mod} 4 的结果,然后 Bob 就可以通过对同色子图进行二分图染色来还原方案。

这样需要发送长 4×1054\times 10^50101 串,考虑剪枝,不难发现度数 <8<8 的点不用发,那么需要发的长度降到了 m8×2×2=m2=2.5×105\frac{m}{8}\times 2\times 2=\frac{m}{2}=2.5\times 10^5,可以通过本题。

代码如下:

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;
}