卧薪尝胆，厚积薄发。
图
Date: Wed Nov 07 21:21:52 CST 2018
In Category:
Description：
有一张
$n$
个点，
$m$
条边的无向连通图，从图中选出一些边，通过这些边
$a$
和
$b$
连通，
$c$
和
$d$
连通，选出的边尽量少。
$1\leqslant n\leqslant 3000$
Solution：
$1$
：
$a-b,c-d$
的路径不相交，则答案一定是
$a-b,c-d$
的最短路之和。
$2$
：
$a-b,c-d$
的路径相交，则相交部分一定是连续的一段路径，于是
$O(n^2)$
预处理每对点的最短路，再
$O(n^2)$
枚举相交的路径的两端，算一下总长就好了。
以上两种情况所有方案取最小值即可。
Code：
没有代码
In tag:
图论-BFS
Timeline
About
Toolbox
Friends
Copyright © 2020
wjh15101051
ღゝ◡╹)ノ♡