[文章目录]
Description
现给定一张无向图，小白有若干个形如“图中有多少对点它们的最小割的容量不超过x呢”的疑问，小蓝虽然很想回答这些问题，但小蓝最近忙着挖木块，于是作为仍然是小蓝的好友，你又有任务了。
T<=10,n<=150,m<=3000,q<=30
最小割树
找出原图中两个点s，t的最小割，连接s-t，边权为最小割，之后将割开的两个子图分治，递归进行此操作，发现最后连成了一颗树，称为最小割树。
结论：x到y的最小割即为在最小割树上，x到y的路径中边权的最小值。
作用：只需n次dinic，即可求出全图任意两点间的最小割。
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 300
#define M 11000
const int inf=0x3f3f3f3f;
int n,m;
int head[N],to[M],nxt[M],f[M],cnt,mp[N][N];
inline void add(int x,int y,int z)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; f[cnt]=z;
}
int s,t,dis[N];
queue<int>q;
bool bfs()
{
while(!q.empty()) q.pop();
memset(dis,-1,sizeof dis);
q.push(s); dis[s]=0; int x,i;
while(!q.empty())
{
x=q.front(); q.pop();
for(i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==-1)
{
dis[to[i]]=dis[x]+1;
if(to[i]==t) return true;
q.push(to[i]);
}
}
return false;
}
int dinic(int x,int flow)
{
if(x==t) return flow;
int xx,tmp=flow;
for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==dis[x]+1)
{
xx=dinic(to[i],min(tmp,f[i]));
if(!xx) dis[to[i]]=-1;
f[i]-=xx; f[i^1]+=xx; tmp-=xx;
if(!tmp) return flow;
}
return flow-tmp;
}
int p[N],cg[N],g[N*N],tot;
bool vis[N];
void dfs(int x)
{
vis[x]=1;
for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&!vis[to[i]]) dfs(to[i]);
}
void solve(int l,int r)
{
if(l==r) return ;
s=p[l]; t=p[r];
int i,j,tmp=0,i1=l,i2=r;
for(i=2;i<=cnt;i+=2) f[i]=f[i^1]=(f[i]+f[i^1])>>1;
while(bfs()) tmp+=dinic(s,inf);
memset(vis,0,sizeof vis);
dfs(s);
for(i=1;i<=n;++i) if(vis[i])
for(j=1;j<=n;++j) if(!vis[j]&&tmp<mp[i][j])
mp[i][j]=mp[j][i]=tmp;
for(i=l;i<=r;++i)
{
if(vis[p[i]]) cg[i1++]=p[i];
else cg[i2--]=p[i];
}
for(i=l;i<=r;++i) p[i]=cg[i];
solve(l,i2); solve(i1,r);
}
int main()
{
int T; scanf("%d",&T);
while(T--)
{
memset(head,0,sizeof head); cnt=1;
memset(mp,0x3f,sizeof mp);
scanf("%d%d",&n,&m);
int i,j,x,y,z;
for(i=1;i<=m;++i)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
}
for(i=1;i<=n;++i) p[i]=i;
solve(1,n);
for(tot=0,i=1;i<=n;++i)
for(j=i+1;j<=n;++j)
g[++tot]=mp[i][j];
sort(g+1,g+tot+1);
scanf("%d",&z);
while(z--)
{
scanf("%d",&x);
printf("%d\n",upper_bound(g+1,g+tot+1,x)-g-1);
}
puts("");
}
return 0;
}