最小割树

发表于 | 更新于

点对之间不同的最小割至多有n−1n-1种 求一遍最小割，然后继续分治处理S\T集合 ZJOI 2011 最小割 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include "lucida"
using std::fill;
using std::copy;
const int MAXN=150+11,MAXM=3000+11,INF=INT_MAX;
struct Edge *Edge_Pool,*Edge_Me;
struct Edge {
	int to,cap,v;
	Edge *pre,*rev;
	Edge(int to,int cap,Edge *pre):to(to),cap(cap),v(0),pre(pre) {}
	void *operator new(size_t) {
		return Edge_Me++;
	}
}*G[MAXN]={Edge_Pool=Edge_Me=alloc(Edge,MAXM<<1)};int n;
void Reset() {
	for(int pos=1;pos<=n;++pos)
		for(Edge *e=G[pos];e;e=e->pre)
			e->v=0;
}
namespace isap {
	Edge *pree[MAXN],*arc[MAXN];
	int num[MAXN],d[MAXN];
	int Aug(int t) {
		int minf=INF;
		for(Edge *e=pree[t];e;e=pree[e->rev->to])
			chkmn(minf,e->cap-e->v);
		for(Edge *e=pree[t];e;e=pree[e->rev->to]) {
			e->v+=minf;
			e->rev->v-=minf;
		}
		return minf;
	}
	int ISAP(int s,int t) {
		pree[s]=0;
		fill(d+1,d+1+n,0);
		fill(num+1,num+1+n,0);
		copy(G+1,G+1+n,arc+1);
		num[0]=n;
		int flow=0;
		for(int cp=s;d[s]<n;cp=cp==t?(flow+=Aug(t),s):cp) {
			bool adv=0;
			for(Edge *&e=arc[cp];e;e=e->pre)
				if(e->cap>e->v && d[e->to]+1==d[cp]) {
					adv=1;
					pree[cp=e->to]=e;
					break;
				}
			if(!adv) {
				if(!--num[d[cp]])
					break;
				d[cp]=n;
				for(Edge *e=(arc[cp]=G[cp]);e;e=e->pre)
					if(e->cap>e->v) chkmn(d[cp],d[e->to]+1);
				++num[d[cp]];
				if(cp!=s) cp=pree[cp]->rev->to;
			}
		}
		return flow;
	}
}using isap::ISAP;
void Adde(int f,int t,int cap) {
	G[f]=new Edge(t,cap,G[f]);
	G[t]=new Edge(f,cap,G[t]);
	G[f]->rev=G[t];G[t]->rev=G[f];
}
int minCut[MAXN][MAXN],set[MAXN];
bool ud[MAXN];
void DFS(int pos) {
	ud[pos]=1;
	for(Edge *e=G[pos];e;e=e->pre)
		if(e->cap>e->v && !ud[e->to])
			DFS(e->to);
}
void DC(int l,int r) {
	if(l==r) return;
	Reset();
	int flow=ISAP(set[l],set[r]);
	fill(ud+1,ud+1+n,0);
	DFS(set[l]);
	for(int i=1;i<=n;++i) if(ud[i])
		for(int j=1;j<=n;++j) if(!ud[j])
			minCut[j][i]=(chkmn(minCut[i][j],flow),minCut[i][j]);
	static int pset[MAXN];
	int pl=l,pr=r;
	for(int i=l;i<=r;++i)
		pset[ud[set[i]]?pl++:pr--]=set[i];
	copy(pset+l,pset+r+1,set+l);
	DC(l,pl-1);DC(pr+1,r);
}
void Work() {
	Edge_Me=Edge_Pool;
	memset(G,0,sizeof(G));
	int m,Q;is>>n>>m;
	for(int i=1;i<=m;++i) {
		int u,v,c;is>>u>>v>>c;
		Adde(u,v,c);
	}
	for(int i=1;i<=n;++i) {
		set[i]=i;
		fill(minCut[i]+1,minCut[i]+1+n,INF);
	}
	DC(1,n);
	is>>Q;
	for(int loop=1;loop<=Q;++loop) {
		int x;is>>x;
		int Ans=0;
		for(int i=1;i<n;++i)
			for(int j=i+1;j<=n;++j)
				Ans+=minCut[i][j]<=x;
		os<<Ans<<'\n';
	}
}
int main() {
//	freopen("input","r",stdin);
	int T;is>>T;
	while(T--) {
		Work();
		if(T) os<<'\n';
	}
	return 0;
}