【错解】
Hmm不可做啊
要不按b排个序？
然后并查集瞎搞，刷刷刷过了样例
然后大样例大了几万倍
出了组小数据，Successful Hack
弃疗
水过10分
【正解】
用占领的边将顶点连起来，占领联通块的代价为max{max{a},max{c}}·min{b}
随便证一下就会发现实际上就是跑最小生成树的过程
随便维护一下就好了
有环图和路径无关的最优值问题：①缩点 ②生成树
本文共 239 字，大约阅读时间需要 1 分钟。
【错解】
Hmm不可做啊
要不按b排个序？
然后并查集瞎搞，刷刷刷过了样例
然后大样例大了几万倍
出了组小数据，Successful Hack
弃疗
水过10分
【正解】
用占领的边将顶点连起来，占领联通块的代价为max{max{a},max{c}}·min{b}
随便证一下就会发现实际上就是跑最小生成树的过程
随便维护一下就好了
有环图和路径无关的最优值问题：①缩点 ②生成树
转载于:https://www.cnblogs.com/lstoi/p/9817441.html