●BOZJ 2229 [Zjoi2011]最小割

时间：2023-03-09 17:21:16
●BOZJ 2229 [Zjoi2011]最小割

题链：

http://www.lydsy.com/JudgeOnline/problem.php?id=2229

题解：

首先先去看看这个博客：http://blog.****.net/jyxjyx27/article/details/42750833
非常不错的，可以对最小割树有一个简单的感性认识。

由于求最小割树感觉很麻烦，并且本题的点数的数据规模不大，
所以就不需要构造出最小割树，只需要求出所有的 ans[i][j]：i->j的最小割。
即采用分治，求出 n-1个最小割，
并在每次求完最小割后，尝试更新不同集合的点之间的 ans即可。

代码：

#include<queue>

#include<cstdio>

#include<cstring>

#include<iostream>

#define MAXN 200

#define MAXM 7000

#define INF 0x3f3f3f3f

#define filein(x) freopen(#x".in","r",stdin);

#define fileout(x) freopen(#x".out","w",stdout);

using namespace std;

struct Edge{

	int to[MAXM],cap[MAXM],next[MAXM],head[MAXN],ent;

	void Init(){

		ent=2; memset(head,0,sizeof(head));

	}

	void Adde(int u,int v,int w){

		to[ent]=v; cap[ent]=w; next[ent]=head[u]; head[u]=ent++;

		to[ent]=u; cap[ent]=0; next[ent]=head[v]; head[v]=ent++;

	}

	void reset(){

		for(int i=2;i<ent;i+=2){

			cap[i]=cap[i^1]=(cap[i]+cap[i^1])/2;

		}

	}

}E;

bool mark[MAXN];

int a[MAXN],cur[MAXN],d[MAXN],ans[MAXN][MAXN];

int N,M,Q;

bool bfs(int S,int T){

	static queue<int> q; int u,v;

	memset(d,0,sizeof(d));

	d[S]=1; q.push(S);

	while(!q.empty()){

		u=q.front(); q.pop();

		for(int i=E.head[u];i;i=E.next[i]){

			v=E.to[i];

			if(d[v]||!E.cap[i]) continue;

			d[v]=d[u]+1; q.push(v);

		}

	}

	return d[T];

}

int dfs(int u,int reflow,const int &T){

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

	int flowout=0,f,v;

	for(int &i=cur[u];i;i=E.next[i]){

		v=E.to[i];

		if(d[v]!=d[u]+1) continue;

		f=dfs(v,min(reflow,E.cap[i]),T);

		flowout+=f; E.cap[i^1]+=f;

		reflow-=f; E.cap[i]-=f;

		if(!reflow) break;

	}

	if(!flowout) d[u]=0;

	return flowout;

}

int Dinic(int S,int T){

	int flow=0;

	while(bfs(S,T)){

		memcpy(cur,E.head,sizeof(E.head));

		flow+=dfs(S,INF,T);

	}

	return flow;

}

void dfs(int u){

	mark[u]=1;

	for(int i=E.head[u];i;i=E.next[i])

		if(!mark[E.to[i]]&&E.cap[i]) dfs(E.to[i]);

}

void Partition(int l,int r){

	static int tmp[MAXN],S,T,cut;

	if(l>=r) return;

	E.reset(); S=a[l]; T=a[r];

	cut=Dinic(S,T);

	memset(mark,0,sizeof(mark)); dfs(S);

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

		for(int j=1;j<i;j++) if(mark[a[i]]^mark[a[j]])

			ans[a[i]][a[j]]=ans[a[j]][a[i]]=min(ans[a[i]][a[j]],cut);

	int L=l,R=r;

	for(int i=l;i<=r;i++)

		if(mark[a[i]]) tmp[L++]=a[i];

		else tmp[R--]=a[i];

	for(int i=l;i<L;i++) a[i]=tmp[i];

	for(int i=r;i>R;i--) a[i]=tmp[i];

	Partition(l,L-1);

	Partition(R+1,r);

}

int main()

{

	filein(mincut); fileout(mincut);

	int T; scanf("%d",&T);

	while(T--){

		E.Init();

		memset(ans,0x3f,sizeof(ans));

		scanf("%d%d",&N,&M);

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

		for(int i=1,u,v,w;i<=M;i++){

			scanf("%d%d%d",&u,&v,&w);

			E.Adde(u,v,2*w);

		}

		E.reset(); Partition(1,N);

		scanf("%d",&Q);

		for(int k=1,c,num;k<=Q;k++){

			scanf("%d",&c); num=0;

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

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

					if(ans[i][j]<=c) num++;

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

		}

		puts("");

	}

	return 0;

}

相关文章