#P18745. [正睿NOI2021训练] 最小割
[正睿NOI2021训练] 最小割
最小割
串并联图是一张带有源、汇的带权无向图,可以按以下规则构造:
- 一条边,以它的两个端点为源、汇。
- 串联两个串并联图:将第一个图的汇与第二个图的源合并,保留第一个图的源和第二个图的汇。
- 并联两个串并联图:合并两个图的源,再合并两个图的汇。
给定一张 个点、 条边的带权无向图,保证存在两个点作为源、汇,可以将整张图视为上述串并联图。源、汇不直接给出。图中可以有重边,没有自环。
有 次询问,每次给出 ,求将 分到割的两侧时,跨越割的所有边的权值之和的最小值。特别保证,每次询问的 在原图中有直接相连的边。
输入格式
第一行三个整数 。
接下来 行,每行三个整数 ,表示一条权值为 的无向边。
接下来 行,每行两个整数 ,表示询问。
输出格式
输出 行,每行一个整数,表示对应的最小割权值。
数据范围
,,,,,。答案需要 64 位整数。
样例 1
输入
3 3 3
1 2 1
2 3 2
1 3 3
1 2
1 3
2 3
输出
3
4
3