思路:
这题比赛的时候想了好久,最后队友机智的想到了。
不过那时不是我敲的,现在敲的1A。
想好就容易了。
直接把1或者0当做边的权值,然后按边从小到大排序,然后算最小生成用到了几条白边,然后再按边从大到小排序,然后再算白边用了几条。然后最小和最大需要用到的白边都算出来了。如果在这最小最大区间中存在那个啥数列的话就是Yes,否则就是No。
为什么在这区间里面就是对的呢?刚开始我也想了好久,然后发现,因为白边权值是1,然后黑边是0,然后假设用到白边最小的是6,最大的是10,那么,我们可以用黑边去替代两条白边,生成树就是有8条白边了,而正好是我们要找的数列中的数。其实还是有点抽象……自己脑子想想吧……
#include
#include
#include
#include
#include