记录编号	541137	评测结果	AAAAAAAAAAAAAAA
题目名称	[ZJOI 2011] 最小割	最终得分	100
用户昵称	Hale	是否通过	通过
代码语言	C++	运行时间	1.308 s
提交时间	2019-09-05 14:23:48	内存使用	13.97 MiB

#include<bits/stdc++.h>
#define I inline
using namespace std;
const int N=201;
const int M=1e4+7;
const int INF=1e9;
I int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
struct edge
{
	int nx,to,flow,pre;
} e[M];
int head[N],cnt=1,dep[N],n,m,T;
void rebuild()
{
	for (int i=0;i<=cnt;i++) e[i].flow=e[i].pre;
}
void add_edge(int a,int b,int flow)
{
	cnt++;e[cnt].to=b;e[cnt].flow=flow;e[cnt].nx=head[a];e[cnt].pre=flow;head[a]=cnt;
	cnt++;e[cnt].to=a;e[cnt].flow=flow;e[cnt].nx=head[b];e[cnt].pre=flow;head[b]=cnt;
}
bool BFS(int s,int t)
{
	queue<int> que;memset(dep,0,sizeof(dep));
	que.push(s);dep[s]=1;
	while (!que.empty())
	{
		int x=que.front();que.pop();
		for (int i=head[x];i;i=e[i].nx)
		{
			int y=e[i].to;
			if (dep[y]==0&&e[i].flow)
			{
				dep[y]=dep[x]+1;
				que.push(y);
			}
		}
	}
  if (dep[t]==0) return false;
  else return true;
}
int dfs(int x,int limit,int t)
{
	if (x==t) return limit;
	int used=0;
	for (int i=head[x];i;i=e[i].nx)
	{
		int y=e[i].to;
		if (dep[y]==dep[x]+1&&e[i].flow>0)
		{
			int di=dfs(y,min(limit-used,e[i].flow),t);
			if (di>0)
			{
				e[i].flow-=di;
				e[i^1].flow+=di;
				used+=di;
				if (used==limit) return used;
			}
		}
	}
  	if (!used) dep[x]=-2;
  	return used;
}
int dinic(int s,int t)
{
	int ans=0;
	while (BFS(s,t)) ans+=dfs(s,INF,t);
	return ans;
}
bool vis[N];
int a[N],tmp1[N],tmp2[N];
int ans[N][N];
void getnode(int x)
{
	vis[x]=true;
	for (int i=head[x];i;i=e[i].nx)
	if (e[i].flow&&!vis[e[i].to]) getnode(e[i].to);
}
void build(int l,int r)
{
	if (l==r) return;
	rebuild();int s=a[l],t=a[r];
	int D=dinic(s,t);memset(vis,0,sizeof(vis));
	getnode(s);
	for (int i=1;i<=n;i++)
	{
		if (vis[i]) 
		for (int j=1;j<=n;j++)
		if (!vis[j]) ans[i][j]=ans[j][i]=min(ans[i][j],D);
	}
	int t1=0,t2=0;
	for (int i=l;i<=r;i++)
		if (vis[a[i]]) tmp1[++t1]=a[i];
		else tmp2[++t2]=a[i];
	int p=l;
	for (int i=1;i<=t1;i++) a[p++]=tmp1[i];
	for (int i=1;i<=t2;i++) a[p++]=tmp2[i];
	build(l,l+t1-1);build(l+t1,r);
}
int main()
{
	freopen("mincuto.in","r",stdin);
	freopen("mincuto.out","w",stdout); 
	T=read();
	while (T--)
	{
		memset(ans,0x3f3f3f,sizeof(ans));
		memset(head,0,sizeof(head));
		n=read(),m=read();cnt=1;
		for (int i=1;i<=n;i++) a[i]=i;
		for (int i=1;i<=m;i++)
		{
			int x=read(),y=read(),z=read();
			add_edge(x,y,z);
		}
		build(1,n);
		int Q=read();
		while (Q--)
		{
			int x=read(),tot=0;
			for (int i=1;i<=n;i++)
			 for (int j=i+1;j<=n;j++)
			 if (ans[i][j]<=x) tot++;
			printf("%d\n",tot);
		}
		puts(" ");
	}
	return 0;
}