「BZOJ2229」[ZJOI2011] 最小割

2015年1月28日8,7987

Description

小白在图论课上学到了一个新的概念——最小割，下课后小白在笔记本上写下了如下这段话： “对于一个图，某个对图中结点的划分将图中所有结点分成两个部分，如果结点s,t不在同一个部分中，则称这个划分是关于s,t的割。对于带权图来说，将所有顶点处在不同部分的边的权值相加所得到的值定义为这个割的容量，而s,t的最小割指的是在关于s,t的割中容量最小的割” 现给定一张无向图，小白有若干个形如“图中有多少对点它们的最小割的容量不超过x呢”的疑问，小蓝虽然很想回答这些问题，但小蓝最近忙着挖木块，于是作为仍然是小蓝的好友，你又有任务了。

Input

输入文件第一行有且只有一个正整数T，表示测试数据的组数。对于每组测试数据，第一行包含两个整数n,m，表示图的点数和边数。下面m行，每行3个正整数u,v,c(1<=u,v<=n,0<=c<=106)，表示有一条权为c的无向边(u,v) 接下来一行，包含一个整数q，表示询问的个数下面q行，每行一个整数x，其含义同题目描述。

Output

对于每组测试数据，输出应包括q行，第i行表示第i个问题的答案。对于点对(p,q)和(q,p)，只统计一次（见样例）。

两组测试数据之间用空行隔开。

Sample Input

1
5 0
1
0

Sample Output

「数据范围」
对于100%的数据 T<=10,n<=150,m<=3000,q<=30，x在32位有符号整数类型范围内。
图中两个点之间可能有多条边

题解

fhq神犇题解：

首先，注意这样一个事实：如果(X,Y)是某个s1-t1最小割，(Z,W)是某个s2-t2最小割，那么X∩Z、X∩W、Y∩Z、Y∩W这四项不可能均非空。也就是说，最小割不可能相互跨立。

这个蕴含了，最多一共有N-1个不同的s-t最小割。只需把这些割找出来即可。

寻找的方法：首先，在V中任意找两个点a,b，求最大流，把V划分为割X-Y，之后对X、Y分别递归地进行划分。这样就能得到N-1个割了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#define eps 1e-8
#define inf 1000000000
#define pa pair<int,int>
#define ll long long 
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int tes,S,T;
int n,m,Q,cnt;
int a[155],tmp[155],last[155],h[155],q[155];
int ans[155][155];
bool mark[155];
struct edge{
	int to,next,v;
}e[100005];
void insert(int u,int v,int w)
{
	e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;
}
bool bfs()
{
	int head=0,tail=1;
	memset(h,-1,sizeof(h));
	h[S]=0;q[0]=S;
	while(head!=tail)
	{
		int now=q[head];head++;
		for(int i=last[now];i;i=e[i].next)
			if(h[e[i].to]==-1&&e[i].v)
			{
				h[e[i].to]=h[now]+1;
				q[tail++]=e[i].to;
			}
	}
	return h[T]!=-1;
}
int dfs(int x,int f)
{
	if(x==T)return f;
	int w,used=0;
	for(int i=last[x];i;i=e[i].next)
		if(h[e[i].to]==h[x]+1)
		{
			w=dfs(e[i].to,min(e[i].v,f-used));
			e[i].v-=w;e[i^1].v+=w;
			used+=w;
			if(used==f)return f;
		}
	if(used==0)h[x]=-1;
	return used;
}
void dfs(int x)
{
	mark[x]=1;
	for(int i=last[x];i;i=e[i].next)
		if(e[i].v&&!mark[e[i].to])
			dfs(e[i].to);
}
int dinic()
{
	int ans=0;
	while(bfs())ans+=dfs(S,inf);
	return ans;
}
void restore()
{
	for(int i=2;i<=cnt;i+=2)
		e[i].v=e[i^1].v=(e[i].v+e[i^1].v)/2;
}
void solve(int l,int r)
{
	if(l==r)return;
	restore();S=a[l];T=a[r];
	int t=0;
	while(bfs())t+=dfs(S,inf);
    memset(mark,0,sizeof(mark));
	dfs(S);
	for(int i=1;i<=n;i++)
		if(mark[i])
			for(int j=1;j<=n;j++)
				if(!mark[j])	
					ans[i][j]=ans[j][i]=min(ans[i][j],t);
	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<=r;i++)a[i]=tmp[i];
	solve(l,L-1);solve(R+1,r);
}
int main()
{
	tes=read();
	while(tes--)
	{
		cnt=1;
		memset(ans,127,sizeof(ans));
		memset(last,0,sizeof(last));
		n=read();m=read();
		for(int i=1;i<=n;i++)a[i]=i;
		for(int i=1;i<=m;i++)
		{
			int u=read(),v=read(),c=read();
			insert(u,v,c);
			insert(v,u,c);
		}
		solve(1,n);
		Q=read();
		while(Q--)
		{
			int c=read(),tot=0;
			for(int i=1;i<=n;i++)
				for(int j=i+1;j<=n;j++)
					if(ans[i][j]<=c)tot++;
			printf("%d\n",tot);
		}
		puts("");
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<ctime>

#include<vector>

#include<queue>

#include<algorithm>

#include<map>

#include<cmath>

#define eps 1e-8

#define inf 1000000000

#define pa pair<int,int>

#define ll long long

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

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

return x*f;

}

int tes,S,T;

int n,m,Q,cnt;

int a[155],tmp[155],last[155],h[155],q[155];

int ans[155][155];

bool mark[155];

struct edge{

int to,next,v;

}e[100005];

void insert(int u,int v,int w)

{

e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;

}

bool bfs()

{

int head=0,tail=1;

memset(h,-1,sizeof(h));

h[S]=0;q[0]=S;

while(head!=tail)

{

int now=q[head];head++;

for(int i=last[now];i;i=e[i].next)

if(h[e[i].to]==-1&&e[i].v)

{

h[e[i].to]=h[now]+1;

q[tail++]=e[i].to;

}

return h[T]!=-1;

}

int dfs(int x,int f)

{

if(x==T)return f;

int w,used=0;

for(int i=last[x];i;i=e[i].next)

if(h[e[i].to]==h[x]+1)

{

w=dfs(e[i].to,min(e[i].v,f-used));

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

used+=w;

if(used==f)return f;

}

if(used==0)h[x]=-1;

return used;

}

void dfs(int x)

{

mark[x]=1;

for(int i=last[x];i;i=e[i].next)

if(e[i].v&&!mark[e[i].to])

dfs(e[i].to);

}

int dinic()

{

int ans=0;

while(bfs())ans+=dfs(S,inf);

return ans;

}

void restore()

{

for(int i=2;i<=cnt;i+=2)

e[i].v=e[i^1].v=(e[i].v+e[i^1].v)/2;

}

void solve(int l,int r)

{

if(l==r)return;

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

int t=0;

while(bfs())t+=dfs(S,inf);

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

dfs(S);

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

if(mark[i])

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

if(!mark[j])

ans[i][j]=ans[j][i]=min(ans[i][j],t);

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<=r;i++)a[i]=tmp[i];

solve(l,L-1);solve(R+1,r);

}

int main()

{

tes=read();

while(tes--)

{

cnt=1;

memset(ans,127,sizeof(ans));

memset(last,0,sizeof(last));

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

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

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

{

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

insert(u,v,c);

insert(v,u,c);

}

solve(1,n);

Q=read();

while(Q--)

{

int c=read(),tot=0;

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

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

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

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

}

puts("");

}

return 0;

}

« 「BZOJ2400」SPOJ 839 Optimal Marks 「BZOJ3144」[HNOI2013] 切糕 »

gzz

求fhq神犇讲解地址
btw，那个结论我好像举出反例了怎么办233

Lvat_s

黄学长您好……请问restore中直接除以2会不会导致答案错误……这样有可能有些容量为奇数边的容量减少1……

梦奇地

在这儿是无向图嘛，一条边和其反向边的残量加起来是一定是这条边容量的二倍咯，除以二就可以得到原来的容量啦。

（这种写法也可以说是巧妙也可以说是懒咯）

hzwer

是这样的

婷小葵葵葵

请问那个事实和得出的结论有什么关系…任意一个A+B=S的划分形式都具有那个性质吧…但可能有2^|S|划分啊…

刘峰玮

orz

Chenyao

Orzzzzzz

hzwer.com _ Home | http://hzwer.com

「BZOJ2229」[ZJOI2011] 最小割

Description

Input

Output

Sample Input

Sample Output

题解

分类目录

热门文章

Myfriends

近期评论