最小割

OI&ACM, 网络流
  1. 1 【bzoj 1412】[ZJOI2009]狼和羊的故事
  2. 2 【bzoj 1497】[NOI2006]最大获利
  3. 3 【bzoj 1934】[Shoi2007]Vote 善意的投票
  4. 4 【bzoj 2132】圈地计划
  5. 5 【bzoj 3894】文理分科
  6. 6 【bzoj 2007】[Noi2010]海拔

算法合集之《最小割模型在信息学竞赛中的应用》

1 【bzoj 1412】[ZJOI2009]狼和羊的故事

Orez的羊狼圈可以看作一个n*m个矩阵格子，这个矩阵的边缘已经装上了篱笆。Orez决定在羊狼圈中再加入一些篱笆，还是要将羊狼分开来养。Orez想要添加篱笆的尽可能的短。当然这个篱笆首先得保证不能改变狼羊的所属领地，再就是篱笆必须修筑完整，也就是说必须修建在单位格子的边界上并且不能只修建一部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <cstdio>
#include <queue>
const int inf=0x7fffffff;
const int N=10005;
int n,m,S,T,ecnt=1,ans,ds[N],head[N],to[6*N],next[6*N],rest[6*N];
std::queue<int> Q;
inline void Addedge(int x,int y,int a,int b)
{
	to[++ecnt]=y;rest[ecnt]=a;next[ecnt]=head[x];head[x]=ecnt;
	to[++ecnt]=x;rest[ecnt]=b;next[ecnt]=head[y];head[y]=ecnt;
}
inline bool Bfs()
{
	for(int i=0;i<=T;i++) ds[i]=0;
	Q.push(S);ds[S]=1;
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();
		for(int e=head[x],y=to[e];e;y=to[e=next[e]])
			if(rest[e]&&!ds[y])
				ds[y]=ds[x]+1,Q.push(y);
	}
	return ds[T];
}
inline int Maxflow(int x,int flow)
{
	if(x==T||!flow) return flow;
	int a=0,b;
	for(int e=head[x],y=to[e];e;y=to[e=next[e]])
		if(rest[e]&&ds[y]==ds[x]+1)
		{
			b=Maxflow(y,std::min(flow-a,rest[e]));
			a+=b;rest[e]-=b;rest[e^1]+=b;
			if(a==flow) break;
		}
	if(!a) ds[x]=0;
	return a;
}
int main()
{
	scanf("%d%d",&n,&m);
	T=n*m+1;
	for(int i=1,num=1,x;i<=n;i++)
		for(int j=1;j<=m;j++,num++)
		{
			scanf("%d",&x);
			if(x==1) Addedge(S,num,inf,0);
			else if(x) Addedge(num,T,inf,0);
			if(j!=1) Addedge(num-1,num,1,1);
			if(i!=1) Addedge(num-m,num,1,1);
		}
	while(Bfs()) ans+=Maxflow(S,inf);
	printf("%d",ans);
}

2 【bzoj 1497】[NOI2006]最大获利

一共N个可以作为通讯信号中转站的地址，建立第i个通讯中转站需要的成本为Pi（1≤i≤N）。另外公司调查得出了所有期望中的用户群，一共M个。关于第i个用户群的信息概括为Ai, Bi和Ci：这些用户会使用中转站Ai和中转站Bi进行通讯，公司可以获益Ci。（1≤i≤M, 1≤Ai, Bi≤N）。如何选择最终建立的中转站才能让公司的净获利最大呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <cstdio>
#include <queue>
const int inf=0x7fffffff;
const int N=55005;
const int M=320000;
int n,m,S,T,ecnt=1,ans,ds[N],head[N],to[M],next[M],rest[M];
std::queue<int> Q;
inline void Addedge(int x,int y,int r)
{
	to[++ecnt]=y;rest[ecnt]=r;next[ecnt]=head[x];head[x]=ecnt;
	to[++ecnt]=x;rest[ecnt]=0;next[ecnt]=head[y];head[y]=ecnt;
}
inline bool Bfs()
{
	for(int i=0;i<=T;i++) ds[i]=0;
	Q.push(S);ds[S]=1;
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();
		for(int e=head[x],y=to[e];e;y=to[e=next[e]])
			if(rest[e]&&!ds[y])
				ds[y]=ds[x]+1,Q.push(y);
	}
	return ds[T];
}
inline int Maxflow(int x,int flow)
{
	if(x==T||!flow) return flow;
	int a=0,b;
	for(int e=head[x],y=to[e];e;y=to[e=next[e]])
		if(rest[e]&&ds[y]==ds[x]+1)
		{
			b=Maxflow(y,std::min(flow-a,rest[e]));
			a+=b;rest[e]-=b;rest[e^1]+=b;
			if(a==flow) break;
		}
	if(!a) ds[x]=0;
	return a;
}
int main()
{
	scanf("%d%d",&n,&m);
	T=n+m+1;
	for(int i=1,x;i<=n;i++)
		scanf("%d",&x),Addedge(S,i,x);
	for(int i=1,x,y,z;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		Addedge(x,n+i,inf);
		Addedge(y,n+i,inf);
		Addedge(n+i,T,z);
		ans+=z;
	}
	while(Bfs()) ans-=Maxflow(S,inf);
	printf("%d",ans);
}

3 【bzoj 1934】[Shoi2007]Vote 善意的投票

n个人，冲突数为好朋友之间发生冲突的总数加上和所有和自己本来意愿发生冲突的人数。 求最小冲突数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <cstdio>
#include <queue>
int n,m,S,T,ecnt=1,ans,ds[305],head[305],to[90500],next[90500],rest[90500];
std::queue<int> Q;
inline void Addedge(int x,int y,int a,int b)
{
	to[++ecnt]=y;rest[ecnt]=a;next[ecnt]=head[x];head[x]=ecnt;
	to[++ecnt]=x;rest[ecnt]=b;next[ecnt]=head[y];head[y]=ecnt;
}
inline bool Bfs()
{
	for(int i=0;i<=T;i++) ds[i]=0;
	Q.push(S);ds[S]=1;
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();
		for(int e=head[x],y=to[e];e;y=to[e=next[e]])
			if(rest[e]&&!ds[y])
				ds[y]=ds[x]+1,Q.push(y);
	}
	return ds[T];
}
inline int Maxflow(int x,int flow)
{
	if(x==T||!flow) return flow;
	int a=0,b;
	for(int e=head[x],y=to[e];e;y=to[e=next[e]])
		if(rest[e]&&ds[y]==ds[x]+1)
		{
			b=Maxflow(y,std::min(flow-a,rest[e]));
			a+=b;rest[e]-=b;rest[e^1]+=b;
			if(a==flow) break;
		}
	if(!a) ds[x]=0;
	return a;
}
int main()
{
	scanf("%d%d",&n,&m);
	T=n+1;
	for(int i=1,x;i<=n;i++)
	{
		scanf("%d",&x);
		if(!x) Addedge(S,i,1,0);
		else Addedge(i,T,1,0);
	}
	for(int i=1,x,y;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		Addedge(x,y,1,1);
	}
	while(Bfs()) ans+=Maxflow(S,0x7fffffff);
	printf("%d",ans);
}

4 【bzoj 2132】圈地计划

将N×M的矩阵分为商业区和工业区。对于第i行第j列的区域，建造商业区将得到Aij收益，建造工业区将得到Bij收益。另外不同的区域连在一起可以得到额外的收益，即如果区域(i,j)相邻（相邻是指两个格子有公共边）有K块（显然K不超过4）类型不同于(i,j)的区域，则这块区域能增加K×Cij收益。求收益最大的方案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <cstdio>
#include <queue>
const int N=10005;
int n,m,S,T,ecnt=1,ans,a[N],b[N],c[N],ds[N],head[N],to[8*N],next[8*N],rest[8*N];
std::queue<int> Q;
inline void Addedge(int x,int y,int r,int f)
{
	ans+=r;
	to[++ecnt]=y;rest[ecnt]=r;next[ecnt]=head[x];head[x]=ecnt;
	to[++ecnt]=x;rest[ecnt]=r*f;next[ecnt]=head[y];head[y]=ecnt;
}
inline bool Bfs()
{
	for(int i=0;i<=T;i++) ds[i]=0;
	Q.push(S);ds[S]=1;
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();
		for(int e=head[x],y=to[e];e;y=to[e=next[e]])
			if(rest[e]&&!ds[y])
				ds[y]=ds[x]+1,Q.push(y);
	}
	return ds[T];
}
inline int Maxflow(int x,int flow)
{
	if(x==T||!flow) return flow;
	int a=0,b;
	for(int e=head[x],y=to[e];e;y=to[e=next[e]])
		if(rest[e]&&ds[y]==ds[x]+1)
		{
			b=Maxflow(y,std::min(flow-a,rest[e]));
			a+=b;rest[e]-=b;rest[e^1]+=b;
			if(a==flow) break;
		}
	if(!a) ds[x]=0;
	return a;
}
int main()
{
	scanf("%d%d",&n,&m);
	T=n*m+1;
	for(int i=1;i<T;i++) scanf("%d",&a[i]);
	for(int i=1;i<T;i++) scanf("%d",&b[i]);
	for(int i=1;i<T;i++) scanf("%d",&c[i]);
	for(int i=1,num=1;i<=n;i++)
		for(int j=1;j<=m;j++,num++)
		{
			if((i+j)&1)
			{
				Addedge(S,num,a[num],0);
				Addedge(num,T,b[num],0);
				if(j!=1) Addedge(num,num-1,c[num]+c[num-1],1);
				if(j!=m) Addedge(num,num+1,c[num]+c[num+1],1);
				if(i!=1) Addedge(num,num-m,c[num]+c[num-m],1);
				if(i!=n) Addedge(num,num+m,c[num]+c[num+m],1);
			}
			else Addedge(S,num,b[num],0),Addedge(num,T,a[num],0);
		}
	while(Bfs()) ans-=Maxflow(S,0x7fffffff);
	printf("%d",ans);
}

5 【bzoj 3894】文理分科

小P所在的班级要进行文理分科。他的班级可以用一个n*m的矩阵进行 描述，每个格子代表一个同学的座位。每位同学必须从文科和理科中选择 一科。同学们在选择科目的时候会获得一个满意值。满意值按如下的方式 得到：
1．如果第i行第秒J的同学选择了文科，则他将获得art[i][j]的满意值，如果选择理科，将得到science[i][j]的满意值。
2．如果第i行第J列的同学选择了文科，并且他相邻（两个格子相邻当且仅当它们拥有一条相同的边）的同学全部选择了文科，则他会更开心，所以会增加same_art[i][j]的满意值。
3．如果第i行第j列的同学选择了理科，并且他相邻的同学全部选择了理科，则增加same_science[i]j[]的满意值。
小P想知道，大家应该如何选择，才能使所有人的满意值之和最大。请 告诉他这个最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <cstdio>
#include <queue>
const int inf=0x7fffffff;
const int N=10005;
int n,m,S,T,ecnt=1,ans,ds[3*N],head[3*N],to[28*N],next[28*N],rest[28*N];
std::queue<int> Q;
inline void Addedge(int x,int y,int r)
{
	to[++ecnt]=y;rest[ecnt]=r;next[ecnt]=head[x];head[x]=ecnt;
	to[++ecnt]=x;rest[ecnt]=0;next[ecnt]=head[y];head[y]=ecnt;
}
inline bool Bfs()
{
	for(int i=0;i<=T;i++) ds[i]=0;
	Q.push(S);ds[S]=1;
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();
		for(int e=head[x],y=to[e];e;y=to[e=next[e]])
			if(rest[e]&&!ds[y])
				ds[y]=ds[x]+1,Q.push(y);
	}
	return ds[T];
}
inline int Maxflow(int x,int flow)
{
	if(x==T||!flow) return flow;
	int a=0,b;
	for(int e=head[x],y=to[e];e;y=to[e=next[e]])
		if(rest[e]&&ds[y]==ds[x]+1)
		{
			b=Maxflow(y,std::min(flow-a,rest[e]));
			a+=b;rest[e]-=b;rest[e^1]+=b;
			if(a==flow) break;
		}
	if(!a) ds[x]=0;
	return a;
}
int main()
{
	scanf("%d%d",&n,&m);
	T=n*m*3+1;
	for(int i=1,x;i<=n*m;i++)
		scanf("%d",&x),Addedge(S,i,x),ans+=x;
	for(int i=1,x;i<=n*m;i++)
		scanf("%d",&x),Addedge(i,T,x),ans+=x;
	for(int i=1,num=1,x;i<=n;i++)
		for(int j=1;j<=m;j++,num++)
		{
			scanf("%d",&x);
			Addedge(S,num+n*m,x);ans+=x;
			Addedge(num+n*m,num,inf);
			if(j!=1) Addedge(num+n*m,num-1,inf);
			if(j!=m) Addedge(num+n*m,num+1,inf);
			if(i!=1) Addedge(num+n*m,num-m,inf);
			if(i!=n) Addedge(num+n*m,num+m,inf);
		}
	for(int i=1,num=1,x;i<=n;i++)
		for(int j=1;j<=m;j++,num++)
		{
			scanf("%d",&x);
			Addedge(num+n*m*2,T,x);ans+=x;
			Addedge(num,num+n*m*2,inf);
			if(j!=1) Addedge(num-1,num+n*m*2,inf);
			if(j!=m) Addedge(num+1,num+n*m*2,inf);
			if(i!=1) Addedge(num-m,num+n*m*2,inf);
			if(i!=n) Addedge(num+m,num+n*m*2,inf);
		}
	while(Bfs()) ans-=Maxflow(S,inf);
	printf("%d",ans);
}

6 【bzoj 2007】[Noi2010]海拔

YT市是一个规划良好的城市，城市被东西向和南北向的主干道划分为n×n个区域。简单起见，可以将YT市看作一个正方形，每一个区域也可看作一个正方形。从而，YT城市中包括(n+1)×(n+1)个交叉路口和2n×(n+1)条双向道路（简称道路），每条双向道路连接主干道上两个相邻的交叉路口。下图为一张YT市的地图(n = 2)，城市被划分为2×2个区域，包括3×3个交叉路口和12条双向道路。 小Z作为该市的市长，他根据统计信息得到了每天上班高峰期间YT市每条道路两个方向的人流量，即在高峰期间沿着该方向通过这条道路的人数。每一个交叉路口都有不同的海拔高度值，YT市市民认为爬坡是一件非常累的事情，每向上爬h的高度，就需要消耗h的体力。如果是下坡的话，则不需要耗费体力。因此如果一段道路的终点海拔减去起点海拔的值为h(注意h可能是负数)，那么一个人经过这段路所消耗的体力是max{0, h}（这里max{a, b}表示取a, b两个值中的较大值）。 小Z还测量得到这个城市西北角的交叉路口海拔为0，东南角的交叉路口海拔为1(如上图所示)，但其它交叉路口的海拔高度都无法得知。小Z想知道在最理想的情况下（即你可以任意假设其他路口的海拔高度），每天上班高峰期间所有人爬坡所消耗的总体力和的最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <cstdio>
#include <queue>
#define P std::pair<int,int>
int n,S,T,ecnt=1,head[250005],ds[250005],next[2005000],cost[2005000],to[2005000];
std::priority_queue< P , std::vector< P > , std::greater < P > > Q;
inline void Addedge(int x,int y,int z)
{
	to[++ecnt]=y;cost[ecnt]=z;next[ecnt]=head[x];head[x]=ecnt;
}
inline int Dijkstra()
{
	for(int i=0;i<=T;i++) ds[i]=-1;
	Q.push(std::make_pair(0,S));
	while(!Q.empty())
	{
		int x=Q.top().second,d=Q.top().first;Q.pop();
		if(ds[x]!=-1) continue;
		ds[x]=d;
		for(int e=head[x];e;e=next[e])
			Q.push(std::make_pair(d+cost[e],to[e]));
	}
	return ds[T];
}
int main()
{
	scanf("%d",&n);T=n*n+1;
	for(int i=1,num=1,x;i<=n+1;i++)
		for(int j=1;j<=n;j++,num++)
			scanf("%d",&x),Addedge(std::max(num-n,S),std::min(num,T),x);
	for(int i=1,num=1,x;i<=n;i++,num--)
		for(int j=1;j<=n+1;j++,num++)
			scanf("%d",&x),Addedge(j<=n?num:S,j>1?num-1:T,x);
	for(int i=1,num=1,x;i<=n+1;i++)
		for(int j=1;j<=n;j++,num++)
			scanf("%d",&x),Addedge(std::min(num,T),std::max(num-n,S),x);
	for(int i=1,num=1,x;i<=n;i++,num--)
		for(int j=1;j<=n+1;j++,num++)
			scanf("%d",&x),Addedge(j>1?num-1:T,j<=n?num:S,x);
	printf("%d",Dijkstra());
}