记录编号	469292	评测结果	AAAAAAAAAAAAAAA
题目名称	[ZJOI 2011] 最小割	最终得分	100
用户昵称	泪寒之雪	是否通过	通过
代码语言	C++	运行时间	1.059 s
提交时间	2017-11-02 21:28:16	内存使用	0.53 MiB

#include<bits/stdc++.h>
#define eho(x) for(int& i=hed[x];~i;i=net[i])
#define Eho(x) for(int i=head[x];~i;i=net[i])
#define N 187
#define M 6607
#define SIZ 171
#define sight(c) (c<='9'&&c>='0')
#define INF (1<<29)
using namespace std;
int T,n,m,A,B,CO,s,t,x,y,z;
int Dp[SIZ][SIZ],X,Y,q,ans,id[N],tmp[N];
char c;
void read(int &x) {
	c=getchar();
	for(; !sight(c); c=getchar());
	for(x=0; sight(c); c=getchar()) x=(x<<3)+(x<<1)+c-48;
}
struct G {
	int head[N],net[M],fall[M],cost[M],s,t,tot,d[N],hed[N],cost2[M];
	bool in[N];
	queue<int> Q;
	G() {}
	inline void updata() {
		memcpy(cost,cost2,sizeof cost);	
	}
	inline void cpy() {
		memcpy(cost2,cost,sizeof cost);
	}
	inline void clear() {
		memset(head,-1,sizeof head); memset(net,-1,sizeof net); tot=-1;}
	inline void add(int x,int y,int c) {
		fall[++tot]=y; net[tot]=head[x]; head[x]=tot; cost[tot]=c;}
	inline void adds(int x,int y,int c) {
		add(x,y,c); add(y,x,c);}
	inline bool spfa() {
		memset(d,127,sizeof d);
		int x; d[s]=1; Q.push(s); in[s]=1;
		while (!Q.empty()) {
			x=Q.front(); Q.pop();
			Eho(x)
			if (cost[i]&&d[fall[i]]>d[x]+1) {
				d[fall[i]]=d[x]+1;
				if (!in[fall[i]]) {
					in[fall[i]]=1,Q.push(fall[i]);}
			}
			in[x]=0;
		}
		return d[t]<INF;
	}
	inline int dfs(int x,int F) {
		if (x==t|| !F) return F;
		int flow=0,r;
		eho(x)
		if (d[x]+1==d[fall[i]]&&((r=dfs(fall[i],min(F,cost[i])))>0)) {
			cost[i]-=r; cost[i^1]+=r;
			F-=r; flow+=r;
			if (!F) break;
		}
		return flow;
	}
	int dinic(int A,int B) {
		s=A; t=B;
		int flow=0;
		while (spfa()) {
			memcpy(hed,head,sizeof head);
			flow+=dfs(s,INF);
		}
		return flow;
	}
} G;
void sol(int L,int R){
	if (L==R) return;
    G.updata();
	int ret=G.dinic(id[L],id[R]),l=L,r=R;
    for(int i=1;i<=n;i++)if(G.d[i]<INF){
        for(int j=1;j<=n;j++)if(G.d[j]>INF) Dp[i][j]=Dp[j][i]=min(Dp[i][j],ret);
    }
    for(int i=L;i<=R;i++) tmp[(G.d[id[i]]<INF)?l++:r--]=id[i];
    for(int i=L;i<=R;i++) id[i]=tmp[i];
    sol(L,r);sol(l,R);
}
int main () {
	freopen("mincuto.in","r",stdin);
	freopen("mincuto.out","w",stdout);
	read(T);
	while (T--){
		G.clear(); read(n); read(m);
		memset(Dp,127,sizeof Dp);
		while (m--) {
			read(X);read(Y);read(CO);
			G.adds(X,Y,CO);
		}
		for (int i=1;i<=n;i++) id[i]=i;
		G.cpy();
		sol(1,n);
	    read(q);
	    while (q--) {
	    	read(x); ans=0;
	    	for (int i=1;i<n;i++)
	    	 for (int j=i+1;j<=n;j++)
	    	  if (x>=Dp[i][j]) ans++;
	    	printf("%d\n",ans);
		}
	  if (T) putchar('\n');
	}
	return 0;
}