整体二分部分一个无法理解的错误
查看原帖
整体二分部分一个无法理解的错误
161697
ღꦿ࿐楼主2023/12/26 12:18

这段代码是我本题的整体二分部分的实现,我认为没有问题但无法通过此题,改成题解的逻辑就能通过了,但我认为我的逻辑没有问题,求大佬答疑。

inline void solve (int l,int r,std :: vector <node> es) {
	if (l == r) {
		for (auto E : es) 
			cn[l].emplace_back (E.u , E.v) ;
		return ;
	}
	int mid = (l + r) >> 1; 
	std :: vector <node> ls , rs; 
	for (auto E : es) 
		if (E.t > mid) 
			scc :: adde (dsu :: find(E.u) , dsu :: find(E.v));	
	scc :: solve () ;
	int tim = dsu :: op ;
	
	for (auto E : es) {
		if (E.t > mid) {
			if (scc :: bel[dsu :: find(E.u)] != scc :: bel[dsu :: find(E.v)]) 
				ls.push_back (E) ; // 如果只加入后面的边不能连通,放到左边寻找更靠前的时间。 
			else 
				dsu :: 	merge (dsu :: find(E.u) , dsu :: find(E.v)) , 
				rs.push_back (E) ; // 如果之加入后面的边已经连通了,放到右边寻找更靠后的时间,同时将连通性以并查集的形式放到左边。 
		}
		else {			
			if (scc :: bel[dsu :: find(E.u)] != scc :: bel[dsu :: find(E.v)]) 
				ls.push_back (E) ; //  没有连通,试图寻找更左边的时间是否连通 。 
			else 
				cn[E.t].emplace_back (E.u , E.v) ; // 如果只加入了 mid右边这些边都连通了,那么加入这条边的时候它的左右就一定连通了,不继续下放。 
		}
	}
		
	scc :: clear () ;
	solve (l , mid , ls) ;
	dsu :: recall (tim) ;
	
	solve (mid + 1 , r , rs) ;
}

这是题解下放部分的逻辑

	for (auto E : es) {
		if (E.t > mid) {
			if (scc :: bel[dsu :: find(E.u)] != scc :: bel[dsu :: find(E.v)]) 
				ls.push_back (E) ; // 如果只加入后面的边不能连通,放到左边寻找更靠前的时间。 
			else 
				dsu :: 	merge (dsu :: find(E.u) , dsu :: find(E.v)) , 
				rs.push_back (E) ; // 如果之加入后面的边已经连通了,放到右边寻找更靠后的时间,同时将连通性以并查集的形式放到左边。 
		}
		else {			
			ls.push_back (E) ; //  以为是再更左边出现的,所以不管连不连通直接丢给左边。 
		}
	}
		

这是完整的代码

2023/12/26 12:18
加载中...