題目鏈接：bzoj點(diǎn)我:-) 洛谷點(diǎn)我:-) 題目描述： 小白在圖論課上學(xué)到了一個(gè)新的概念——最小割，下課后小白在筆記本上寫下了如下這段話： ”對(duì)于一個(gè)圖，某個(gè)對(duì)圖中結(jié)點(diǎn)的劃分將圖中所有結(jié)點(diǎn)分成兩個(gè)部分，如果結(jié)點(diǎn)s,t不在同一個(gè)部分中，則稱這個(gè)劃分是關(guān)于s,t的割。 對(duì)于帶權(quán)圖來說，將所有頂點(diǎn)處在不同部分的邊的權(quán)值相加所得到的值定義為這個(gè)割的容量，而s,t的最小割指的是在關(guān)于s,t的割中容量最小的割“ 現(xiàn)給定一張無向圖，小白有若干個(gè)形如”圖中有多少對(duì)點(diǎn)它們的最小割的容量不超過x呢“的疑問，小藍(lán)雖然很想回答這些問題，但小藍(lán)最近忙著挖木塊，于是作為仍然是小藍(lán)的好友，你又有任務(wù)了。

輸入格式： 輸入文件第一行有且只有一個(gè)正整數(shù)T，表示測(cè)試數(shù)據(jù)的組數(shù)。 對(duì)于每組測(cè)試數(shù)據(jù)， 第一行包含兩個(gè)整數(shù)n,m，表示圖的點(diǎn)數(shù)和邊數(shù)。 下面m行，每行3個(gè)正整數(shù)u,v,c(1<=u,v<=n,0<=c<=106$10^6$)，表示有一條權(quán)為c的無向邊(u,v) 接下來一行，包含一個(gè)整數(shù)q，表示詢問的個(gè)數(shù) 下面q行，每行一個(gè)整數(shù)x，其含義同題目描述。

輸出格式： 對(duì)于每組測(cè)試數(shù)據(jù)，輸出應(yīng)包括q行，第i行表示第i個(gè)問題的答案。對(duì)于點(diǎn)對(duì)(p,q)和(q,p)，只統(tǒng)計(jì)一次（見樣例）。兩組測(cè)試數(shù)據(jù)之間用空行隔開。

思路： 最小割樹的裸題。（入門的講解） 最小割樹性質(zhì)：若不考慮多個(gè)最小割的情況，設(shè)S1-T1的最小割割集為C1，S2-T2的最小割割集為C2，則C1，C2必然不會(huì)相互跨立，這個(gè)結(jié)論可通過反證法得到（是可以感性證明一下的）。 它們構(gòu)成了一棵最小割樹，每次挑兩個(gè)點(diǎn)算MInCut分成兩個(gè)集合分治算即可，最小割數(shù)目不超過n?1$n-1$

所以Dinic+分治，但是isap不知道為什么RE了（爆棧？）。。

感想： 又一次深夜刷的題。。昨天1點(diǎn)多鐘還在WA，整個(gè)人都不好了，早上發(fā)現(xiàn)。。居然忘了在跟新答案時(shí)賦成雙向。（論剛開始連題目都沒看懂并且不知道割是什么的我。。好吧割集是刪掉這個(gè)集合中的任意一條邊，會(huì)使那兩個(gè)點(diǎn)不聯(lián)通） 終于又有動(dòng)力做題了，終于知道看到別人刷題記錄時(shí)的強(qiáng)大動(dòng)力了>-<

代碼：