青岛oj集训5
Floyd算法——全源最短路cerr:标准输出错误流：不会输出到freopen制定的out文件中，而是会输出到错误文件中。
提交上去无论加不加freopen，哪怕是提交到洛谷，也只是比较out文件中的值，而不会管cerr输出的东西
好处：调试的时候用cerr，哪怕忘删调试调试
例题1：传递闭包
floyd可以直接算，但复杂度太高
压缩：用bitset优化
bool：00000001/00000000
bitset：1/0
bool&bool运算时间：O（n）
bitset&bitset：O（n/w）（w是机器字长，一般考试是64，即优化速度快了64倍）
这里看一下这的算法：
假设有一条1-2-3-4的链
f=1100,即能到达12点，到不了34
1:1100 由于这里1能够到达2if(f)成立，才能用2去更新1的所有可达点
2:1110
————
1:1110
3：0111
————
1:1111
这样经过两轮更新，就能到34了
（p.s：其实实际上不是逮着一个点一直更新它，这样可能有更新不到的情况。实际上是先用一个点去更新所有可达点（先枚举k））
例题二：灾后重建
方法一：把所有讯问离线下来，按照t升序进行回答，在排回去
但是这道题保证了Q次讯问的t是不降的，所以就不用离线下来排序了
而且村庄标号越大，解封时间越晚
所以直接枚举点的标号就是解封顺序
用k来代表目前解封到第几个点了
当kv
然后先跑一遍传递闭包，求出所有可达点
如果i可以到达j点，那么说明i可以拿到j的礼物
最后就输出每一个奶牛，如果它能拿到愿望清单上的1号礼物，就输出1号（不一定就是礼物1，只是排名最靠前的那个）
如果能，就输出完了broke掉，否则就下一个，直到找到最靠前的（肯定能找到的，毕竟自己到自己要设为可达）
代码吗……嘿嘿，手速慢没截到，要不那个时候的我（不会吧？我的博文还有除我以外的人看？）再补上？嘻嘻……反正坑是填不完的嘛
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]