6
29
2015
2

【bzoj2229】[Zjoi2011]最小割

首先学习一下fhq的最小割树理论

应该是比较好理解的,然后只需要求n此最小割就可以得到任意两点之间的最小割了,因为大错一个字母然后拜样例所赐一直在疯狂的wa然后……然后&然后就没有了

//coder : davidwang
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <climits>
#include <queue>
#include <deque>
#include <iostream>
#include <stack>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <vector>
#include <algorithm>
using namespace std;
#define LL long long
#define PII pair<int,int>
#define X first
#define Y second
inline int read()
{
	int ret=0,f=1; char ch;
	for (ch=getchar();ch<'0' || ch>'9';ch=getchar())
		if (ch=='-') f=-f;
	for (;'0'<=ch && ch<='9';ch=getchar())
		ret=ret*10+ch-'0';
	return ret*f;
}
const int N = 155,M=3010;
struct edge{
	int to,flow;
	edge(int to=0,int flow=0):to(to),flow(flow){}
}e[M*2];
vector<int>g[N];
int vis[N],q[N],d[N],cnt;
inline void connect(int x,int y,int f){
	e[cnt]=edge(y,f); g[x].push_back(cnt++);
	e[cnt]=edge(x,f); g[y].push_back(cnt++);
}
int s,t,n,m;
int bfs(){
	int head=0,tail=1,u,v;
	memset(d,0,sizeof(d));
	q[1]=s; d[s]=1;
	while (head<tail){
		u=q[++head];
		for (vector<int>::iterator it=g[u].begin();it!=g[u].end();it++){
			if (e[*it].flow && d[e[*it].to]==0){
				d[e[*it].to]=d[u]+1;
				q[++tail]=e[*it].to;
			}
		}
	}
	return d[t];
}
int dfs(int x,int flow){
	if (x==t || flow==0) return flow;
	int f,totflow=0;
	for (vector<int>::iterator it=g[x].begin();it!=g[x].end();it++){
		if (e[*it].flow && d[e[*it].to]==d[x]+1){
			f=dfs(e[*it].to,min(flow,e[*it].flow));
			totflow+=f; flow-=f;
			e[*it].flow-=f; e[(*it)^1].flow+=f;
			if (flow==0) return totflow;
		}
	}
	if (flow)d[x]=0;
	return totflow;
}
inline int dinic()
{
	int ret=0;
	while (bfs()) ret+=dfs(s,INT_MAX);
	return ret;
}
			
int ans[N][N];
inline void rebuild(){
	for (int i=0;i<cnt;i+=2)
		e[i].flow=e[i+1].flow=(e[i].flow+e[i+1].flow)/2;	
}
int a[N],list[N];
void solve(int l,int r){
	if (l==r) return;
	rebuild();
	s=a[l],t=a[r];
	int Flow=dinic();
	for (int i=1;i<=n;i++)
		if (d[i])
			for (int j=1;j<=n;j++)
				if (d[j]==0)
					ans[i][j]=ans[j][i]=min(ans[i][j],Flow);
	int L=l,R=r;
	for (int i=l;i<=r;i++){
		if (d[a[i]])
			list[L++]=a[i];
		else list[R--]=a[i];
	}
	for (int i=l;i<=r;i++) a[i]=list[i];
	solve(l,L-1); solve(R+1,r);
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
#endif
	int T=read();
	while (T--){
		cnt=0; for (int i=1;i<=n;i++) g[i].clear();
		memset(ans,127,sizeof(ans));
		n=read(); m=read();
		for (int i=1;i<=m;i++){
			int x=read(),y=read(),z=read();
			connect(x,y,z);
		}
		for (int i=1;i<=n;i++) a[i]=i;
		solve(1,n);
		int Q=read();
		while (Q--){
			int now=read(),ret=0;
			for (int i=1;i<=n;i++)
				for (int j=i+1;j<=n;j++)
					if (ans[i][j]<=now) ret++;
			printf("%d\n",ret);
		}
		puts("");
	}
	return 0;
}

 

Category: 未分类 | Tags: bzoj 最小割 最小割树 | Read Count: 1046
Avatar_small
Joel Cramsie 说:
2019年2月19日 13:37

The lists of the programmers are prepared for the goodwill of the computer specialists. The role of the program and top rated professional resume writers is advanced in the midst of the skills. The abilities are met for the occupational challenges for the citizens in the whole of the scheme of the program.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com