【BZOJ2229】[ZJOI2011]最小割（网络流，最小割树）

时间：2023-03-09 13:12:10
【BZOJ2229】[ZJOI2011]最小割（网络流，最小割树）

【BZOJ2229】[ZJOI2011]最小割（网络流，最小割树）

题面

BZOJ

洛谷

题解

戳这里

那么实现过程就是任选两点跑最小割更新答案，然后把点集划分为和\(S\)联通以及与\(T\)联通。

然后再这两个点集里面分别任选两点跑最小割，递归下去即可。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<queue>

using namespace std;

#define MAX 200

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

struct Line{int v,next,w,W;}e[8000];

int h[MAX],cnt;

inline void Add(int u,int v,int w)

{

	e[cnt]=(Line){v,h[u],w,w};h[u]=cnt++;

	e[cnt]=(Line){u,h[v],w,w};h[v]=cnt++;

}

void rebuild(){for(int i=0;i<=cnt;++i)e[i].w=e[i].W;}

int n,m;

int level[MAX],S,T;

bool bfs()

{

	memset(level,0,sizeof(level));level[S]=1;

	queue<int> Q;Q.push(S);

	while(!Q.empty())

	{

		int u=Q.front();Q.pop();

		for(int i=h[u];i;i=e[i].next)

			if(e[i].w&&!level[e[i].v])

				level[e[i].v]=level[u]+1,Q.push(e[i].v);

	}

	return level[T];

}

int dfs(int u,int flow)

{

	if(u==T||!flow)return flow;

	int ret=0;

	for(int i=h[u];i;i=e[i].next)

	{

		int v=e[i].v,d;

		if(e[i].w&&level[v]==level[u]+1)

		{

			d=dfs(v,min(flow,e[i].w));

			flow-=d;ret+=d;

			e[i].w-=d;e[i^1].w+=d;

		}

	}

	return ret;

}

int Dinic()

{

	int ret=0;

	while(bfs())ret+=dfs(S,1e9);

	return ret;

}

bool vis[MAX];

int a[MAX],tmp1[MAX],tmp2[MAX];

int ans[MAX][MAX];

void getnode(int u)

{

	vis[u]=true;

	for(int i=h[u];i;i=e[i].next)

		if(e[i].w&&!vis[e[i].v])getnode(e[i].v);

}

void Solve(int l,int r)

{

	if(l==r)return;

	rebuild();S=a[l];T=a[r];

	int d=Dinic();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];

	Solve(l,l+t1-1);Solve(l+t1,r);

}

int main()

{

	int T=read();

	while(T--)

	{

		memset(ans,63,sizeof(ans));

		memset(h,0,sizeof(h));cnt=2;

		n=read();m=read();

		for(int i=1;i<=m;++i)

		{

			int u=read(),v=read(),w=read();

			Add(u,v,w);

		}

		for(int i=1;i<=n;++i)a[i]=i;

		Solve(1,n);

		int Q=read();

		while(Q--)

		{

			int u=read(),tot=0;

			for(int i=1;i<=n;++i)

				for(int j=i+1;j<=n;++j)

					if(ans[i][j]<=u)++tot;

			printf("%d\n",tot);

		}

		puts("");

	}

	return 0;

}

相关文章