G题分情况讨论,第一,s和t的路径上只有一条b边,那么我考虑枚举每条边权值为b的边,然后两端和st的连通性。第二s和t路径上会有多条b边,那么我考虑所有权值为b的边会形成若干个连通块,我要在每个连通块里判断s和t能不能靠小于b的边连到同一个连通块里。这里用带权并查集进行判断,以及按秩合并(小的插到大的里面)来保证单log的复杂度。并查集构建过程种,从小到大的遍历边就可以。
点赞

相关推荐

牛客网
牛客网在线编程
牛客网题解
牛客企业服务