A2373. 最小割
编程题
省选/NOI-
知识点
题目描述
小白在图论课上学到了一个新的概念——最小割，下课后小白在笔记本上写下了如下这段话：
对于一个图，某个对图中结点的划分将图中所有结点分成两个部分，如果结点 $s$ 和 $t$ 不在同一个部分中，则称这个划分是关于 $s,t$ 的割。对于带权图来说，将所有顶点处在不同部分的边的权值相加所得到的值定义为这个割的容量，而 $s,t$ 的最小割指的是在关于 $s,t$ 的割中容量最小的割。
现给定一张无向图，小白有若干个形如“图中有多少个无序点对的最小割的容量不超过 $x$ ”的疑问，小蓝虽然很想回答这些问题，但小蓝最近忙着挖木块，于是作为小蓝的好友，你又有任务了。
对于一个图，某个对图中结点的划分将图中所有结点分成两个部分，如果结点 $s$ 和 $t$ 不在同一个部分中，则称这个划分是关于 $s,t$ 的割。对于带权图来说，将所有顶点处在不同部分的边的权值相加所得到的值定义为这个割的容量，而 $s,t$ 的最小割指的是在关于 $s,t$ 的割中容量最小的割。
现给定一张无向图，小白有若干个形如“图中有多少个无序点对的最小割的容量不超过 $x$ ”的疑问，小蓝虽然很想回答这些问题，但小蓝最近忙着挖木块，于是作为小蓝的好友，你又有任务了。
输入格式
**本题有多组测试数据。**
第一行一个整数 $T$，表示测试数据组数。
对于每组测试数据，第一行两个整数 $n,m$，表示图的点数和边数。
接下来 $m$ 行，每行三个整数 $u,v,c$ 表示有一条权为 $c$ 的无向边 $(u,v)$。不保证图中无重边。
接下来一行一个整数 $q$ 表示询问的个数，下面 $q$ 行每行一个整数 $x$ 描述一组询问。
第一行一个整数 $T$，表示测试数据组数。
对于每组测试数据，第一行两个整数 $n,m$，表示图的点数和边数。
接下来 $m$ 行，每行三个整数 $u,v,c$ 表示有一条权为 $c$ 的无向边 $(u,v)$。不保证图中无重边。
接下来一行一个整数 $q$ 表示询问的个数，下面 $q$ 行每行一个整数 $x$ 描述一组询问。
输出格式
对于每一组测试数据输出 $q$ 行，每行一个整数表示对应询问的答案。对于满足条件的点对 $(p,q)$ 和点对 $(q,p)$ 只应该在答案中统计一次。
**在两组测试数据之间需要输出一行空行。**
**在两组测试数据之间需要输出一行空行。**
输入输出样例
输入 #1
1 5 0 1 0
输出 #1
10
说明/提示
对于 $100 \%$ 的数据，$1 \leq T \leq 10$，$1 \leq n \leq 150$，$0 \leq m \leq 3000$，$0 \leq x \leq 2^{31}-1$，$0 \leq q \leq 30$。