P1967 货车运输
- 唔快下课啦我先写写思路吧qwq
- 显然对于每辆货车经过的路径中，边权最小的边越大，答案越优 ——>先求一个最大生成树保证树上的边边权值都尽可能大
- 因为求了最大生成树，所以两点之间的路径唯一——>可以用倍增求lca的方法求出货车的运输路径，更新路径上边权最小值即答案qwq
- 有可能两个点不连通， 并查集找一下他们的爸爸qwq就可以啦，输出“-1”
- 现在还有个小问题QAQ，怎么在倍增的时候更新边权最小值啊啊啊啊啊QAQ
- 现在要去吃饭啦回来再起飞！biu~~~ //11.43
【noip系列——图论】货车运输
总之岁月漫长，然而值得期待。