【20181019T3】比特战争【最小生成树思想】
题面
【错解】
Hmm不可做啊
要不按b排个序？
然后并查集瞎搞，刷刷刷过了样例
然后大样例大了几万倍
出了组小数据，Successful Hack
弃疗
水过10分
【正解】
用占领的边将顶点连起来，占领联通块的代价为max{max{a},max{c}}·min{b}
随便证一下就会发现实际上就是跑最小生成树的过程
随便维护一下就好了
代码
有环图和路径无关的最优值问题：①缩点 ②生成树
【【20181019T3】比特战争【最小生成树思想】】转载于:https://www.cnblogs.com/lstoi/p/9817441.html
推荐阅读
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗（）
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境，人生还很长