标题是偷的

求大佬康康,不知怎么的爆零了

应该是在main函数里面出错的

因为这个模板拿去交[最小割树模板]是能过的

#include <bits/stdc++.h>
using namespace std;
const int inf=1e9;
const int maxn=1e5+10;
struct edge{
	int to,nxt,flow;
}d[maxn]; int head[maxn],cnt=1;
void add(int u,int v,int flow)
{
	d[++cnt]=(edge){ v,head[u],flow },head[u]=cnt;
	d[++cnt]=(edge){ u,head[v],0},head[v]=cnt;
}
int dis[maxn],n,m;
bool bfs(int s,int t)
{
	for(int i=0;i<=n+1;i++)	dis[i]=0;
	dis[s]=1;
	queue<int>q; q.push( s );
	while( !q.empty() )
	{
		int u=q.front(); q.pop();
		for(int i=head[u];i;i=d[i].nxt )
		{
			int v=d[i].to;
			if( dis[v]==0&&d[i].flow )
			{
				dis[v]=dis[u]+1;
				if( v==t )	return true;
				q.push( v ); 
			}
		}
	}
	return false;
}
int dinic(int u,int t,int flow)
{
	if( u==t )	return flow;
	int res=flow;
	for(int i=head[u];i;i=d[i].nxt )
	{
		int v=d[i].to;
		if( dis[v]==dis[u]+1&&d[i].flow )
		{
			int temp=dinic(v,t,min(d[i].flow,res) );
			res-=temp;
			if( temp==0 )	dis[v]=0;
			d[i].flow-=temp;
			d[i^1].flow+=temp;
		}
		if( res==0 )	break;
	}
	return flow-res;
}
void init()
{
	for(int i=2;i<=cnt;i+=2)//撤流操作,复原上一次最大流的影响 
		d[i].flow+=d[i^1].flow,d[i^1].flow=0;
}
int maxflow(int s,int t)
{
	init();
	int ans=0;
	while( bfs(s,t) )	ans+=dinic(s,t,inf);
	return ans;
}
class GHT
{
	public:
		edge d[maxn];
		int head[maxn],cnt;
		int temp1[maxn],temp2[maxn],node[maxn];
		void add(int u,int v,int flow){
			d[++cnt]=(edge){ v,head[u],flow },head[u]=cnt;
			d[++cnt]=(edge){ u,head[v],flow },head[v]=cnt;
		}
		void build(int l,int r)
		{
			if( l>=r )	return;
			int x=node[l],y=node[l+1];//随便拉两个点跑最小割
			int cut = maxflow(x,y);
			add(x,y,cut);
			//去掉x和y,分成temp1和temp2两个集合
			int top1=0,top2=0;
			for(int i=l;i<=r;i++)
			{
				//最后一次bfs后有深度,说明s和这个点相连接
				if( dis[ node[i] ] )	temp1[++top1]=node[i];
				else	temp2[++top2]=node[i];	
			}
			for(int i=l;i<=l+top1-1;i++)	node[i]=temp1[i-l+1];
			for(int i=l+top1;i<=r;i++)	node[i]=temp2[i-top1-l+1]; 
			build(l,l+top1-1); build(l+top1,r);
		}
		int deep[maxn],fa[maxn][23],ans[maxn][23],log2n;
		void dfs(int x,int father)
		{
			fa[x][0]=father;
			deep[x]=deep[father]+1;
			for(int i=1;i<=log2n;i++)
			{
				fa[x][i]=fa[ fa[x][i-1] ][i-1];
				ans[x][i]=min( ans[x][i-1],ans[ fa[x][i-1] ][i-1]);
			}
			for(int i=head[x];i;i=d[i].nxt )
			{
				int v=d[i].to;
				if( v==father )	continue;
				ans[v][0]=d[i].flow;
				dfs(v,x);
			}
		}
		int query(int x,int y)
		{
			int zhi=inf;
			if( deep[x]<deep[y] )	swap(x,y);
			for(int i=log2n;i>=0;i-- )
				if( deep[ fa[x][i] ]>=deep[y] )
				{
					zhi=min(zhi,ans[x][i] );
					x=fa[x][i];
				}
			if( x==y )	return zhi;
			for(int i=log2n;i>=0;i-- )
				if( fa[x][i]!=fa[y][i] )
				{
					zhi=min( zhi,min( ans[x][i],ans[y][i] ) );
					x=fa[x][i],y=fa[y][i];
				}
			zhi=min( zhi,min( ans[x][0],ans[y][0] ));
			return zhi;
		}
}CUT;
void CUT_init()
{
	CUT.log2n=log2(n)+1;
	CUT.cnt=1;
	for(int i=1;i<=500;i++)	CUT.node[i]=i,CUT.head[i]=0,deep[i]=0;
	for(int i=1;i<=500;i++)
	for(int j=0;j<=20;j++)
		CUT.ans[i][j]=CUT.fa[i][j]=0;
	CUT.build(1,n);
	CUT.dfs(1,0);
}
int bridge[maxn],id;
int main()
{
	int T; cin >> T;
	while( T-- )
	{
		cin >> n >> m;
		for(int i=1;i<=m;i++)
		{
			int l,r,flow; cin >> l >> r >> flow;
			add(l,r,flow); add(r,l,flow);
		}
		CUT_init();
		for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			bridge[++id]=CUT.query(i,j);
		int q; cin >> q;
		while( q-- )
		{
			int x; cin >> x;
			x = upper_bound(bridge+1,bridge+1+id,x )-bridge-1;
			cout << x << '\n';
		}
		cout << '\n';
		id=0,cnt=1;
		for(int i=1;i<=n;i++)	head[i]=0;
		memset(bridge,0,sizeof(bridge));
	}
}