关于BFS+异或(C++)
今天早上,我们做了场比赛,里面有一个题目是这样的。。
题目大意:
随着马场的繁荣,出现了越来越多的新马种。种族之间的沟通不畅严重影响了马场的和谐。这时,科学家发明了马语翻译机器人,正好可以解决这一难题。
机器人有 M 种,每种机器人能完成 K 个马种之间的语言翻译。问,利用这些机器人,能否实现 1 种群和 N 种群的马语翻译。 若可以,找到翻译过程至少需要用到多少种语言。
解析:
其实这道题目用最短路跑一片就可以了,无需任何玩意儿。。。。
但是我还是桀骜不驯,来吧,召唤白番薯(BFS)!!
其实BFS与最短路(spfa)差不多,但是对于最短路来说,我还是喜欢BFS(因为我背过板子)
问题:
初次看这到题目时,我的心里还是有点懵逼。。。。
所以还是要看看标的。。。。
但是最重要的就是"我卢本伟没有扣标!!!!!!!"
给大家伙们看看我遇到的问题吧:
void bfs()
{
int head = ,tail = ;
q[] = ;
vis[] = ;
while (head ^ tail) //蓝色
{
int x = q[++head];
for (int j = lnk[x];j;j = nxt[j])
if (!vis[son[j]])
{
vis[son[j]] = ;
dis[son[j]] = dis[x] + ;
q[++tail] = son[j];
}
}
}
就是那蓝蓝的玩意儿!!!!
那是啥?????
于是
一波询问
终于
搞懂了
"Please start your AK show"
解决:
先来普及一下异或:
i xor j
看这个玩意儿↑
诶!!!
打住!!!
这可是c++专场,Pascal怎么进来了(快走!!!);
i ^ j
这才对!!
看:
a⊕b = (¬a ∧ b) ∨ (a ∧¬b)
如果a、b两个值不相同,则异或结果为1。如果a、b两个值相同,异或结果为0。
现在到BFS了
void BFS()
{
int head=;
int tail=;
while(head^tail)
{
//Lazy to write labels...........
}
}
一般循环里都是head<tail的
可是他不是
我瞬间懵了。。。
后来才知道
如果head==tail
则为FALSE
不然为
TRUE
这我才知道
相信你也懂了!!!!
(一直bb)
最后
我只想说,作比赛有好多人都预知未来。。。。
bye~~~
最新文章
- 一个简易的四则运算单元...(15.12.15 BUG更新)
- C++ 非阻塞套接字的使用 (1)
- Topology and Geometry in OpenCascade-Vertex
- Idea的Git使用
- ImageSwitcher 右向左滑动的实现方式
- Xamarin Mono错误: unable to find explicit activity class
- Shell-WEB目录监控
- SpringMVC经典系列-12基于SpringMVC的文件上传---【LinusZhu】
- String,StringBuffer,StringBuilder个人认为较重要的区别
- 27.QT-QProgressBar动态实现多彩进度条(详解)
- 批量 truncate 表
- JavaWeb之Servlet中ServletConfig和ServletContext
- 1877. [SDOI2009]晨跑【费用流】
- WhatsApp &; Tasker for Android – Read &; Write messages
- 011-HQL中级1-Hive快捷查询:不启用Mapreduce job启用Fetch task三种方式介绍
- nej+regular环境使用es6的低成本方案
- Objective-C中,ARC下的 strong和weak指针原理解释
- 小程序组件与api
- (41)C#异步编程
- break 用法