#P4897. 【模板】最小割树(Gomory-Hu Tree)
【模板】最小割树(Gomory-Hu Tree)
题目背景
模板题。做本题之前请确保你会 Dinic 或 ISAP。如果你乱搞过了我请你抽烟。
根据惯例,网络流题不允许卡 Dinic/ISAP,但可以卡 EK,本题数据严格遵循上述条约。
题目描述
给定一个 个点 条边的无向连通图,编号 ,多次询问两点之间的最小割。
两点间的最小割是这样定义的:原图的每条边有一个割断它的代价,你需要用最小的代价使得这两个点不连通。
输入格式
第一行两个数 。
接下来 行,每行 个数 ,表示有一条连接 与 的无向边,割断它的代价为 。
接下来这一行有一个整数 ,表示询问次数。
接下来 行,每行两个数 ,你需要求出 与 之间的最小割。
输出格式
输出共 行,每行一个整数对应询问的答案。
4 5
0 1 2
1 2 2
3 1 3
3 2 1
0 2 1
3
0 3
1 3
1 2
3
4
4
提示
保证 ,,,,。