模板题。做本题之前请确保你会 Dinic 或 ISAP。如果你乱搞过了我请你抽烟。
根据惯例,网络流题不允许卡 Dinic/ISAP,但可以卡 EK,本题数据严格遵循上述条约。
给定一个 n 个点 m 条边的无向连通图,多次询问两点之间的最小割。
两点间的最小割是这样定义的:原图的每条边有一个割断它的代价,你需要用最小的代价使得这两个点不连通。
接下来 m 行,每行 3 个数 u,v,w,表示有一条连接 u 与 v 的无向边,割断它的代价为 w。
接下来这一行有一个整数Q,表示询问次数
接下来 Q 行,每行两个数 u,v,你需要求出 u 与 v 之间的最小割
输出共 Q 行,每行一个整数对应询问的答案
4 5 1 2 2 2 3 2 4 2 3 4 3 1 1 3 1 3 1 4 2 4 2 3
3 4 4
1\le n\leq 500,\quad 0\le m\leq 1500,\quad 0\le Q\leq 10^5,\quad 0\leq w\leq 10^4,\quad u\neq v
模板