#PQJ68x10769. QOJ 68_10769

    ID: 3024 传统题 1000ms 128MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:ZJOI 2011网络流分治

QOJ 68_10769

最小割(mincut) 【题目描述】 小白在图论课上学到了一个新的概念——最小割,下课后小白在笔记本上 写下了如下这段话: “对于一个图,某个对图中结点的划分将图中所有结点分成两个部分,如果 结点s,t 不在同一个部分中,则称这个划分是关于s,t 的割。 对于带权图来说,将所有顶点处在不同部分的边的权值相加所得到的值定 义为这个割的容量,而s,t 的最小割指的是在关于s,t 的割中容量最小的割” 现给定一张无向图,小白有若干个形如“图中有多少对点它们的最小割的 容量不超过x 呢”的疑问,小蓝虽然很想回答这些问题,但小蓝最近忙着挖木块, 于是作为仍然是小蓝的好友,你又有任务了。

【输入说明】 输入文件第一行有且只有一个正整数T,表示测试数据的组数。 对于每组测试数据, 第一行包含两个整数n,m,表示图的点数和边数。 下面m 行,每行3 个正整数u,v,c(1<=u,v<=n,0<=c<=106),表示有一条权为 c 的无向边(u,v) 接下来一行,包含一个整数q,表示询问的个数 下面q 行,每行一个整数x,其含义同题目描述。 【输出说明】 对于每组测试数据,输出应包括q 行,第i 行表示第i 个问题的答案。对 于点对(p,q)和(q,p),只统计一次(见样例)。 【样例输入】 1 5 0 1 0 【样例输出】 10

【数据范围】 对于30%的数据 n<=40,m<=400,q<=10 对于100%的数据 T<=10,n<=150,m<=3000,q<=30,x 在32 位有符号整数类 型范围内。 图中两个点之间可能有多条边