#P4897. 【模板】最小割树(Gomory-Hu Tree)

    ID: 3904 Type: RemoteJudge 500ms 125MiB Tried: 0 Accepted: 0 Difficulty: 6 Uploaded By: Tags>网络流深度优先搜索,DFS最大流最小割

【模板】最小割树(Gomory-Hu Tree)

题目背景

模板题。做本题之前请确保你会 Dinic 或 ISAP。如果你乱搞过了我请你抽烟。

根据惯例,网络流题不允许卡 Dinic/ISAP,但可以卡 EK,本题数据严格遵循上述条约。

题目描述

给定一个 n+1n+1 个点 mm 条边的无向连通图,编号 0n0\sim n,多次询问两点之间的最小割。

两点间的最小割是这样定义的:原图的每条边有一个割断它的代价,你需要用最小的代价使得这两个点不连通。

输入格式

第一行两个数 n,mn,m

接下来 mm 行,每行 33 个数 u,v,wu,v,w,表示有一条连接 uuvv 的无向边,割断它的代价为 ww

接下来这一行有一个整数 QQ,表示询问次数。

接下来 QQ 行,每行两个数 u,vu,v,你需要求出 uuvv 之间的最小割。

输出格式

输出共 QQ 行,每行一个整数对应询问的答案。

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

提示

保证 1n5001\le n\leq 5000m15000\le m\leq 15000Q1050\le Q\leq 10^50w1040\leq w\leq 10^4uvu\neq v