题链：
http://www.lydsy.com/JudgeOnline/problem.php?id=2229
题解：
首先先去看看这个博客：http://blog.csdn.net/jyxjyx27/article/details/42750833
非常不错的，可以对最小割树有一个简单的感性认识。
由于求最小割树感觉很麻烦，并且本题的点数的数据规模不大，
所以就不需要构造出最小割树，只需要求出所有的 ans[i][j]：i->j的最小割。
即采用分治，求出 n-1个最小割，
并在每次求完最小割后，尝试更新不同集合的点之间的 ans即可。
代码：
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#define MAXN 200
#define MAXM 7000
#define INF 0x3f3f3f3f
#define filein(x) freopen(#x".in","r",stdin);
#define fileout(x) freopen(#x".out","w",stdout);
using namespace std;
struct Edge{
int to[MAXM],cap[MAXM],next[MAXM],head[MAXN],ent;
void Init(){
ent=2; memset(head,0,sizeof(head));
}
void Adde(int u,int v,int w){
to[ent]=v; cap[ent]=w; next[ent]=head[u]; head[u]=ent++;
to[ent]=u; cap[ent]=0; next[ent]=head[v]; head[v]=ent++;
}
void reset(){
for(int i=2;i<ent;i+=2){
cap[i]=cap[i^1]=(cap[i]+cap[i^1])/2;
}
}
}E;
bool mark[MAXN];
int a[MAXN],cur[MAXN],d[MAXN],ans[MAXN][MAXN];
int N,M,Q;
bool bfs(int S,int T){
static queue<int> q; int u,v;
memset(d,0,sizeof(d));
d[S]=1; q.push(S);
while(!q.empty()){
u=q.front(); q.pop();
for(int i=E.head[u];i;i=E.next[i]){
v=E.to[i];
if(d[v]||!E.cap[i]) continue;
d[v]=d[u]+1; q.push(v);
}
}
return d[T];
}
int dfs(int u,int reflow,const int &T){
if(u==T||!reflow) return reflow;
int flowout=0,f,v;
for(int &i=cur[u];i;i=E.next[i]){
v=E.to[i];
if(d[v]!=d[u]+1) continue;
f=dfs(v,min(reflow,E.cap[i]),T);
flowout+=f; E.cap[i^1]+=f;
reflow-=f; E.cap[i]-=f;
if(!reflow) break;
}
if(!flowout) d[u]=0;
return flowout;
}
int Dinic(int S,int T){
int flow=0;
while(bfs(S,T)){
memcpy(cur,E.head,sizeof(E.head));
flow+=dfs(S,INF,T);
}
return flow;
}
void dfs(int u){
mark[u]=1;
for(int i=E.head[u];i;i=E.next[i])
if(!mark[E.to[i]]&&E.cap[i]) dfs(E.to[i]);
}
void Partition(int l,int r){
static int tmp[MAXN],S,T,cut;
if(l>=r) return;
E.reset(); S=a[l]; T=a[r];
cut=Dinic(S,T);
memset(mark,0,sizeof(mark)); dfs(S);
for(int i=1;i<=N;i++)
for(int j=1;j<i;j++) if(mark[a[i]]^mark[a[j]])
ans[a[i]][a[j]]=ans[a[j]][a[i]]=min(ans[a[i]][a[j]],cut);
int L=l,R=r;
for(int i=l;i<=r;i++)
if(mark[a[i]]) tmp[L++]=a[i];
else tmp[R--]=a[i];
for(int i=l;i<L;i++) a[i]=tmp[i];
for(int i=r;i>R;i--) a[i]=tmp[i];
Partition(l,L-1);
Partition(R+1,r);
}
int main()
{
filein(mincut); fileout(mincut);
int T; scanf("%d",&T);
while(T--){
E.Init();
memset(ans,0x3f,sizeof(ans));
scanf("%d%d",&N,&M);
for(int i=1;i<=N;i++) a[i]=i;
for(int i=1,u,v,w;i<=M;i++){
scanf("%d%d%d",&u,&v,&w);
E.Adde(u,v,2*w);
}
E.reset(); Partition(1,N);
scanf("%d",&Q);
for(int k=1,c,num;k<=Q;k++){
scanf("%d",&c); num=0;
for(int i=1;i<=N;i++)
for(int j=1;j<i;j++)
if(ans[i][j]<=c) num++;
printf("%d
",num);
}
puts("");
}
return 0;
}