ICPC沈阳46-B-Bitwise Exclusive-OR Sequence

链接：

https://ac.nowcoder.com/acm/contest/24346/B

题意：

n个点(n个数字)，m个关系

每条关系包含u,v,w，表示au异或(XOR)av等于w

要求构建一个符合关系的和最小数组，没有符合的输出-1

PS：数组元素非负

解：

第一次写ICPC的补题题解，蒟蒻人的错误请多指教

比赛的时候没写出来，以为是要让出入度最大的点承担异或中更大的部分（即对所有和这个点所有w去&，然后给这个点）

然后被出入度相同的点的优先顺序卡住了

后来请教了一下我滴罗神

罗神：要拆成二进制看，在每一位上，对每一份连通图，都可以默认一个起点的这一位为0，然后根据这位上的关系，构建出这一位上确定的连通图（因为拆成二进制所以图里只有0和1），构造不出来就是非法

因为我使用的是queue>存储带权双向边，所以用bfs更合适（用过的边直接pop抛出，就不会重复，但是就不合适dfs）

#include
#include
using namespace std;
typedef long long int ll;
const int nSize=1E5+5;
const int mSize=2E5+10;
queue>mp[nSize];
ll sz[nSize];//数组
bool book[nSize];//
int yes=1;//成立状态
ll ans[31][2];//记录每一位上0和1的数量
setacl; //连通图记录器
void csh(int b=0)//初始化
{
	memset(sz,b,sizeof(sz));
}
void add(int u,int v,int w)//双向带权边添加，queue>mp[nSize];
{
	mp[u].push(pair(v,w));
	mp[v].push(pair(u,w));
}

数组初始化-1，遍历每个点，如果没有处理过就加入处理

处理完以后，就能得到这个连通图不一定最小的一个合法构建（不合法直接更新全局变量，使结果为-1）

罗神：对于这个合法构造，二进制每一位上，可以让所有1变成0，所有0变成1，所以对于这份构造的图，每一位上选0和1数量少的一个置为1

我：为什么呢QWQ

因为如果这个连通图构造合法，那么点0和点1的关系是在这一位上异或为1，点0和点0、点1和点1在这一位上的关系都是异或等于0

这时候0变1,1变0，还是能保证图的合法性，我们要让数组最小，所以让这一位上的1最少，即选取构造好的图中这一位上0和1数量少的一个设置为1

for(int i=1;i<=n;i++)//进入处理环节 
	{
		if(sz[i]==-1)//没有处理过
		{
		    acl.clear();//清空连通图记录器
			cl(i);//进入处理
			for(auto mao:acl)//遍历连通图
			{
			    if(sz[mao]==-1) continue;//还是-1的点抛弃不记录答案（实际上这个连通图只要能合法的构建，不会有-1的点）
		        else
		        {
			        for(int j=0;j<31;j++)//对每一位进行处理
			        {
			     	   ans[j][((sz[mao]>>j)&1)]++;//第j位上0或1的数量
			        }
		        }
            }
            for(int i=0;i<31;i++)//对每一位取答案
		    {
			    sum+=(ll)(min(ans[i][0],ans[i][1]))*(1< 
处理就是普通的bfs(如果连接的点是-1[没被赋值]，就给根据这一边上的权给他赋一个值，两个点都有值，就异或一下验证是否满足这一边上的权，不满足就是非法构造)–>（一开始是觉得默认一个值是0会不会导致原本能构造出来的图变成非法构造了，后来发现因为每一位上的0和1可以互换，所以没关系）
 
罗神是对二进制每一位的每一份连通图都处理，同时计算答案
 
我是直接整个数字的每一份连通图进行处理，然后再对连通图中每一位计算答案
 
完整代码:
 
ZT:答案正确 通过全部用例 运行时间313ms 占用内存82492KB
 
#include
#include
using namespace std;
typedef long long int ll;
const int nSize=1E5+5;
const int mSize=2E5+10;
queue>mp[nSize];
ll sz[nSize];
bool book[nSize];
int yes=1;
ll ans[31][2];
setacl; 
void csh(int b=0)
{
	memset(sz,b,sizeof(sz));
}
void add(int u,int v,int w)
{
	mp[u].push(pair(v,w));
	mp[v].push(pair(u,w));
}
void cl(int beg)
{
	queuepd;
	pd.push(beg);
	for(;!pd.empty();)
	{
		int mao=pd.front();pd.pop();
		acl.insert(mao);
		if(sz[mao]==-1) sz[beg]=0;
		//cout<<"front"<temp=mp[mao].front();mp[mao].pop();
			//cout<<"first"<>n;//n个节点 
	int m;
	cin>>m;//m个关系 
	csh(-1);//全-1赋值 
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		//cin>>u>>v>>w;
		scanf("%d%d%d",&u,&v,&w);//输入关系 
		add(u,v,w);//载入关系 
		add(v,u,w);//载入关系 
	}
	for(int i=1;i<=n;i++)//进入处理环节 
	{
		if(sz[i]==-1)
		{
		    acl.clear();
			cl(i);
			for(auto mao:acl)
			{
			    //cout<"<"<<((sz[i]>>j)&1)<>j)&1)]++;
			        }
		        }
            }
            for(int i=0;i<31;i++)
		    {
			    sum+=(ll)(min(ans[i][0],ans[i][1]))*(1<"< 
限制：
 
时间限制：C/C++ 1秒
 空间限制：C/C++ 524288K
 64bit IO Format: %lld