POJ21677 / QOJ141 染色 做题记录

通信题，Alice 和 Bob 会收到同一个 $n$ 个点 $m$ 条边的无向图，Alice 会额外收到这个图的一个合法 $8$ 染色。Alice 要向 Bob 发一个长度小于等于 $2.5\times 10^5$ 的 $01$ 串，Bob 需要根据这个 $01$ 串还原出任意一个合法的 $8$ 染色方案。

$1\le n\le 2\times 10^5$，$1\le m\le 5\times 10^5$。

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

这样需要发送长 $4\times 10^5$ 的 $01$ 串，考虑剪枝，不难发现度数 $<8$ 的点不用发，那么需要发的长度降到了 $\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;
}