p3931专题

洛谷P3931 SAC E#1 - 一道难题 Tree (最大流/最小割)

2020.7.11 今天晚上还有比赛,打完这场就不打了,从五月到今天天天刷题也太自闭了,一定得出去玩一阵子。 这道题貌似并不难,带权的有根树,问树根到叶节点不连通的最小代价(要素察觉),那么不就是把树根连源,叶子连汇然后跑一边最大流不就行了??交上去wa到只剩20,后来注意到给出的边的顺序不一定是树里面的顺序,所以肯定需要处理一下才行。我说我今天写这道题的时候怎么有种树链剖分的感觉呢??处理手法