ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

第 46 届 ICPC 国际大学生程序设计竞赛亚洲区域赛(沈阳)B.Bitwise Exclusive-OR Sequence(二分图染色 + dfs)

2022年9月5日 151点热度 1人点赞 0条评论

题目链接:B-Bitwise Exclusive-OR Sequence_第 46 届 ICPC 国际大学生程序设计竞赛亚洲区域赛(沈阳) (nowcoder.com)

题意 / Problem

给定N个点,M条边,点权未知但是每条边上的边权就是其所连接的两个点的点权的异或和。问怎样规划点权可以使得所有点的点权加和最小,输出最小和。

注意:图不一定连通。(这个特别坑!!!)

思路 / Thought

将一个点的点权通过二进制位划分,我们知道不同位之间是相互独立的。又因为这个图未必连通,所以我们不妨假设有3块(举个例子),那么就先给第一块跑二分图,将其对结果的贡献加上,再将计数器清零,给第二块跑二分图.....以此类推,也就是说每个点都不能落下,而不同块之间也是相互独立的。

具体实现看代码,注意dfs时应该判断是否出现矛盾,如果有矛盾直接返回-1,结束程序。

代码 / Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 9;
struct Edge{int x, w;};
vector<Edge> g[maxn];
int N, M, cnt[2], col[maxn];

bool dfs(int x,int i,int o)//o表示color 
{
	col[x] = o, cnt[o] ++;
	bool res = true;
	for(auto &j : g[x])
	{
		int y = j.x, w = j.w;
		if(col[y] != -1)
		{
			//注意这里的col[x]和col[y]表示的不是权值
			//而是一个0或1,所以要把w向右移动i位做异或判断是否为0
			//如果不为0说明产生了矛盾 
			if(col[x] ^ col[y] ^ (w >> i & 1))return false;//出现矛盾 
			continue;//已经走过 
		}
		//res将所有递归的子结果做且运算 
		if(w >> i & 1)res = res && dfs(y, i, o ^ 1);
		else res = res && dfs(y, i, o);
		
		if(!res)break;
	}
	return res;
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N >> M;
	while(M --)
	{
		int u, v, w;cin >> u >> v >> w;
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}
	
	int sum = 0;
	bool tag = true;//表示答案合法 
	
	for(int i = 0;i < 30 && tag; ++ i)//考虑第i位 
	{
		memset(col, -1, sizeof col);
		for(int j = 1;j <= N; ++ j)
		{
			cnt[0] = cnt[1] = 0;//计数器清零,开始计算一个新的连通块 
			if(col[j] != -1)continue;//如果某个点已经被计算过,直接跳过 
			tag = tag && dfs(j, i, 0);//计算新的连通块大小,更新cnt[0]和[1] 
			sum += min(cnt[0], cnt[1]) << i;
		}
	}
	cout << (tag ? sum : -1) << '\n';
	
	return 0;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ dfs icpc 二分图染色 思维 牛客网 算法竞赛
最后更新:2022年9月5日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 题意 / Problem
  • 思路 / Thought
  • 代码 / Code

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号