图论选做

先开个坑.

有一张图 $Graph(n, m)$ , 现在给定 $n, m$ , 要求你通过 $2m$ 次询问一个边集的最大生成树森林权值和, 得到整张图的最小生成树森林权值和.

$n\le 200, m\le 500$

最小生成树题基本模拟Kru或Br, 随便想想就知道不会是Br, 所以考虑Kru.

考虑从小往大加边, 那么一条边是否加入就直接判断已经得到的边集再加上这条边的最大生成树森林是不是原来的值加上这条边的边权, 如果是就加上, 否则说明它把另一条边顶下去了. 于是就先 $m$ 次问每一条的边权, 再 $m$ 次加边即可.

很套路.