网络流

OI&ACM, 网络流
  1. Dinic
  2. 1 【poj 1273】Drainage Ditches
  3. 2 【bzoj 1001】[BeiJing2006]狼抓兔子
  4. 3 【COGS 14】[网络流24题] 搭配飞行员
  5. 4 【COGS 727】[网络流24题] 太空飞行计划
  6. 5 【COGS 728】[网络流24题] 最小路径覆盖问题
  7. 6 【COGS 396】[网络流24题] 魔术球问题（简化版）
  8. 7 【COGS 729】[网络流24题] 圆桌聚餐
  9. 8 【COGS 731】[网络流24题] 最长递增子序列
  10. 9 【COGS 734】[网络流24题] 方格取数问题
  11. 10 【COGS 461】[网络流24题] 餐巾
  12. 11 【SGU 194】Reactor Cooling

Dinic

详解

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
#include<cstdio>
#include<queue>
using namespace std;
const int N=5005;
const int M=10005;
int n,m,S,T,ans,tot=1,ds[N],st[N],to[M*2],rest[M*2],next[M*2];
queue<int> Q;
void Addedge(int x,int y,int z)
{
	to[++tot]=y;rest[tot]=z;next[tot]=st[x];st[x]=tot;
	to[++tot]=x;rest[tot]=0;next[tot]=st[y];st[y]=tot;
}
bool Bfs()
{
	for(int i=0;i<=T;i++) ds[i]=-1;
	Q.push(S);ds[S]=0;
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();
		for(int i=st[x];i;i=next[i])
		  if(rest[i]&&ds[to[i]]==-1)
		    ds[to[i]]=ds[x]+1,Q.push(to[i]);
	}
	return ds[T]>-1;
}
int Dfs(int x,int flow)
{
	if(x==T) return flow;
	int a=0,b;
	for(int i=st[x];i;i=next[i])
	  if(rest[i]&&ds[to[i]]==ds[x]+1)
	  {
	  	b=Dfs(to[i],min(flow-a,rest[i]));
	  	rest[i]-=b;rest[i^1]+=b;a+=b;
	  	if(a==flow) break;
	  }
	if(!a) ds[x]=-1;
	return a;
}
int main()
{
	scanf("%d%d%d",&m,&S,&T);
	for(int i=1,x,y,z;i<=m;i++)
	  scanf("%d%d%d",&x,&y,&z),Addedge(x,y,z);
	while(Bfs()) ans+=Dfs(S,0x7fffffff);
	printf("%d\n",ans);
}

1 【poj 1273】Drainage Ditches

中文翻译
多组数据+有重边，依然阻挡不了它成为模板题。。。

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
#include<cstdio>
#include<queue>
using namespace std;
const int N=205;
queue<int> Q;
int n,m,ans,tot,ds[N],head[N],to[N*2],rest[N*2],next[N*2];
void Addedge(int x,int y,int z)
{
	to[++tot]=y;rest[tot]=z;next[tot]=head[x];head[x]=tot;
	to[++tot]=x;rest[tot]=0;next[tot]=head[y];head[y]=tot;
}
bool BFS()
{
	for(int i=1;i<=m;i++) ds[i]=-1;
	Q.push(1);ds[1]=0;
	while(!Q.empty())
	{
		int x=Q.front(); Q.pop();
		for(int i=head[x];i;i=next[i])
		  if(rest[i]&&ds[to[i]]==-1)
		    ds[to[i]]=ds[x]+1,Q.push(to[i]);
	}
	return ds[m]>-1;
}
int DFS(int x,int flow)
{
	if(x==m) return flow;
	int a=0,b;
	for(int i=head[x];i;i=next[i])
	  if(rest[i]&&ds[to[i]]==ds[x]+1)
	  {
	  	b=DFS(to[i],min(flow-a,rest[i]));
	  	rest[i]-=b;rest[i^1]+=b;
	  	a+=b;
	  	if(a==flow) return flow;
	  }
	if(!a) ds[x]=-1;
	return a;
}
int main()
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		ans=0;tot=1;
		for(int i=1;i<=m;i++) head[i]=0;
		for(int i=1,x,y,z;i<=n;i++)
	      scanf("%d%d%d",&x,&y,&z),Addedge(x,y,z);
	    while(BFS()) ans+=DFS(1,0x7fffffff);
	    printf("%d\n",ans);
	}
}

2 【bzoj 1001】[BeiJing2006]狼抓兔子

双向路，问多少只在END的狼才能把从START的兔子一网打尽

注意这是双向路。。。

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
#include<cstdio>
#include<queue>
using namespace std;
int n,m,S,T,ans,tot=1,v,ds[1000001];
int head[1000001],to[6000001],rest[6000001],next[6000001];
queue<int> Q;
void Addedge(int x,int y,int z)
{
	to[++tot]=y;rest[tot]=z;next[tot]=head[x];head[x]=tot;
	to[++tot]=x;rest[tot]=z;next[tot]=head[y];head[y]=tot;
} 
bool Bfs()
{
	for(int i=S;i<=T;i++) ds[i]=-1;
	Q.push(S);ds[S]=0;
	while(!Q.empty())
	{
		int x=Q.front(); Q.pop();
		for(int i=head[x];i;i=next[i])
		  if(rest[i]&&ds[to[i]]==-1)
		    ds[to[i]]=ds[x]+1,Q.push(to[i]);
	}
	return ds[T]>-1;
}
int Dfs(int x,int flow)
{
	if(x==T) return flow;
	int a=0,b;
	for(int i=head[x];i;i=next[i])
	  if(rest[i]&&ds[to[i]]==ds[x]+1)
	  {
		b=Dfs(to[i],min(flow-a,rest[i]));
		rest[i]-=b;rest[i^1]+=b;
		a+=b;
		if(a==flow) return flow;
	  }
	if(!a) ds[x]=-1;
	return a;
}
int main()
{
	scanf("%d%d",&n,&m);S=1;T=n*m;
	for(int i=1;i<=n;i++)
	  for(int j=1;j<m;j++)
	    scanf("%d",&v),Addedge((i-1)*m+j,(i-1)*m+j+1,v);
	for(int i=1;i<n;i++)
	  for(int j=1;j<=m;j++)
	    scanf("%d",&v),Addedge((i-1)*m+j,i*m+j,v);
	for(int i=1;i<n;i++)
	  for(int j=1;j<m;j++)
	    scanf("%d",&v),Addedge((i-1)*m+j,i*m+j+1,v);
	while(Bfs()) ans+=Dfs(S,0x7fffffff);
	printf("%d",ans);
}

3 【COGS 14】[网络流24题] 搭配飞行员

左边正驾驶员，右边副驾驶员，中间连线表示可以配对，问有多少对正负驾驶员

建一个原点，连接所有正驾驶员，边权为1；
中间连接可以配对的正副驾驶员，边权为1；
建一个汇点，连接所有副驾驶员，边权为1。

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
#include<cstdio>
#include<queue>
using namespace std;
int n,m,u,v,S,T,ans,tot=1,ds[205],st[205],rest[6000],next[6000],to[6000];
queue<int> Q;
void Addedge(int x,int y,int z)
{
	to[++tot]=y;rest[tot]=z;next[tot]=st[x];st[x]=tot;
	to[++tot]=x;rest[tot]=0;next[tot]=st[y];st[y]=tot;
}
bool Bfs()
{
	for(int i=1;i<=T;i++) ds[i]=-1;
	Q.push(S);ds[S]=0;
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();
		for(int i=st[x];i;i=next[i])
		  if(rest[i]&&ds[to[i]]==-1)
		    ds[to[i]]=ds[x]+1,Q.push(to[i]);
	}
	return ds[T]>-1;
}
int Dfs(int x,int flow)
{
	if(x==T) return flow;
	int a=0,b;
	for(int i=st[x];i;i=next[i])
	  if(rest[i]&&ds[to[i]]==ds[x]+1)
	  {
	  	b=Dfs(to[i],min(flow-a,rest[i]));
	  	rest[i]-=b;rest[i^1]+=b;a+=b;
	  	if(a==flow) break;
	  }
	if(!a) ds[x]=-1;
	return a;
}
int main()
{
	freopen("flyer.in","r",stdin);
	freopen("flyer.out","w",stdout);
	scanf("%d%d",&n,&m);S=1;T=n+2;
	for(int i=2;i<=m+1;i++) Addedge(S,i,1);
	for(int i=m+2;i<=n+1;i++) Addedge(i,T,1);
	while(scanf("%d%d",&u,&v)!=EOF) Addedge(u+1,v+1,1);
	while(Bfs()) ans+=Dfs(S,0x7fffffff);
	printf("%d",ans);
	return 0;
}

4 【COGS 727】[网络流24题] 太空飞行计划

有一些实验和一些仪器，一个实验需要某些仪器为前提。完成实验Ej可以得到pj美元，配置仪器lk要花费ck美元。求如何净收益最大。

建立一个二分图，左边是实验，右边是仪器。
实验与S相连，边权为实验收益；仪器与T相连，边权为仪器花费；中间实验和仪器用inf连起来
由最大流-最小割定理，答案为实验收益总额-最大流
详见PPT和黑书 

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
#include<cstdio>
using namespace std;
#define min(x,y) x<y?x:y
const int inf=0x7fffffff;
int n,m,v,S,T,tot=1,ans[105],q[205],ds[205],st[205],to[10205],next[10205],rest[10205];
void Addedge(int x,int y,int z)
{
	to[++tot]=y;rest[tot]=z;next[tot]=st[x];st[x]=tot;
	to[++tot]=x;rest[tot]=0;next[tot]=st[y];st[y]=tot;
}
bool Bfs()
{
	for(int i=1;i<=T;i++) ds[i]=-1;
	int l=1,r=1;q[1]=S;ds[S]=0;
	while(l<=r)
	{
		int x=q[l++];
		for(int i=st[x];i;i=next[i])
		  if(rest[i]&&ds[to[i]]==-1)
		    ds[to[i]]=ds[x]+1,q[++r]=to[i];
	}
	return ds[T]>-1;
}
int Dfs(int x,int flow)
{
	if(x==T) return flow;
	int a=0,b;
	for(int i=st[x];i;i=next[i])
	  if(rest[i]&&ds[to[i]]==ds[x]+1)
	  {
	  	b=Dfs(to[i],min(flow-a,rest[i]));
	  	rest[i]-=b;rest[i^1]+=b;a+=b;
	  	if(a==flow) break;
	  }
	if(!a) ds[x]=-1;
	return a;
}
int main()
{
	freopen("shuttle.in","r",stdin);
	freopen("shuttle.out","w",stdout);
	scanf("%d%d",&m,&n);S=m+n+1;T=S+1;
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&v);Addedge(S,i,v);ans[0]+=v;
		while(getchar()==' ') scanf("%d",&v),Addedge(i,m+v,inf);
	}
	for(int i=1;i<=n;i++) scanf("%d",&v),Addedge(i+m,T,v);
	while(Bfs()) ans[0]-=Dfs(S,inf);
	for(int i=1;i<=m;i++) if(ds[i]!=-1) printf("%d ",i);putchar('\n');
	for(int i=1;i<=n;i++) if(ds[i+m]!=-1) printf("%d ",i);
	printf("\n%d",ans[0]);
	return 0;
}

5 【COGS 728】[网络流24题] 最小路径覆盖问题

有向图G=(V,E)，求最小路径覆盖

题上有题解
from hzwer:
将每个点都分别放入xy集合中
如果u到v有一条边,则x集合的u向y集合的v连一条权值inf的边
S向x集合的点连边，权值1，y集合的点向T连边，权值1，做一遍最大流，得出最大匹配数
ans=n-最大匹配
如果无匹配，显然要n条路径才能覆盖所有点，两个点匹配意味着将可以把它们用一条路径覆盖，路径数就可以减1 

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
#include<cstdio>
#include<queue>
using namespace std;
queue<int> Q;
int n,m,S,T,ans,tot=1,ds[305],st[305],to[12700],rest[12700],next[12700];
bool used[155];
void Addedge(int x,int y,int z)
{
	to[++tot]=y;rest[tot]=z;next[tot]=st[x];st[x]=tot;
	to[++tot]=x;rest[tot]=0;next[tot]=st[y];st[y]=tot;
}
bool Bfs()
{
	for(int i=0;i<=T;i++) ds[i]=-1;
	Q.push(S);ds[S]=0;
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();
		for(int i=st[x];i;i=next[i])
		  if(rest[i]&&ds[to[i]]==-1)
		    ds[to[i]]=ds[x]+1,Q.push(to[i]);
	}
	return ds[T]>-1;
}
int Dfs(int x,int flow)
{
	if(x==T) return flow;
	int a=0,b;
	for(int i=st[x];i;i=next[i])
	  if(rest[i]&&ds[to[i]]==ds[x]+1)
	  {
	  	b=Dfs(to[i],min(flow-a,rest[i]));
	  	rest[i]-=b;rest[i^1]+=b;a+=b;
	  	if(a==flow) break;
	  }
	if(!a) ds[x]=-1;
	return a;
}
void Search(int x)
{
	for(int i=st[x];i;i=next[i])
	  if(!rest[i]&&to[i]!=S&&!used[to[i]-n])
	  {
	  	  printf(" %d",to[i]-n);used[to[i]-n]=1;
		  return Search(to[i]-n);
	  }  
}
int main()
{
	freopen("path3.in","r",stdin);
	freopen("path3.out","w",stdout);
	scanf("%d%d",&n,&m);S=n*2+1;T=S+1;ans=n;
	for(int i=1;i<=n;i++) Addedge(S,i,1),Addedge(n+i,T,1);
	for(int i=1,u,v;i<=m;i++) scanf("%d%d",&u,&v),Addedge(u,n+v,1);
	while(Bfs()) ans-=Dfs(S,0x7fffffff);
	for(int i=1;i<=n;i++)
	  if(!used[i])
	    printf("%d",i),Search(i),printf("\n");
	printf("%d\n",ans);
}

6 【COGS 396】[网络流24题] 魔术球问题（简化版）

假设有n根柱子，现要按下述规则在这n根柱子中依次放入编号为 1，2，3，4 ...... 的球。
（1）每次只能在某根柱子的最上面放球。
（2）在同一根柱子中，任何2个相邻球的编号之和为完全平方数。
试设计一个算法，计算出在n根柱子上最多能放多少个球。例如，在4 根柱子上最多可放11个球。

from hzwer：
枚举答案A，在图中建立节点1..A。如果对于i < j有i+j为一个完全平方数，连接一条有向边(i,j)。该图是有向无环图，求最小路径覆盖。如果刚好满足最小路径覆盖数等于N，那么A是一个可行解，在所有可行解中找到最大的A，即为最优解。
具体方法可以顺序枚举A的值，当最小路径覆盖数刚好大于N时终止，A-1就是最优解。 

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
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
int n,S,T,tot=1,ds[3205],st[3205],next[135000],to[135000],rest[135000];
queue<int> Q;
void Addedge(int x,int y,int z)
{
	to[++tot]=y;rest[tot]=z;next[tot]=st[x];st[x]=tot;
	to[++tot]=x;rest[tot]=0;next[tot]=st[y];st[y]=tot;
}
bool Bfs()
{
	for(int i=0;i<=T;i++) ds[i]=-1;
	Q.push(S);ds[S]=0;
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();
		for(int i=st[x];i;i=next[i])
		  if(rest[i]&&ds[to[i]]==-1)
		    ds[to[i]]=ds[x]+1,Q.push(to[i]);
	}
	return ds[T]>-1;
}
int Dfs(int x,int flow)
{
	if(x==T) return flow;
	int a=0,b;
	for(int i=st[x];i;i=next[i])
	  if(rest[i]&&ds[to[i]]==ds[x]+1)
	  {
	  	b=Dfs(to[i],min(flow-a,rest[i]));
	  	rest[i]-=b;rest[i^1]+=b;a+=b;
	  	if(a==flow) break;
	  }
	if(!a) ds[x]=-1;
	return a;
}
int main()
{
	freopen("balla.in","r",stdin);
	freopen("balla.out","w",stdout);
	scanf("%d",&n);S=0;T=3201;
	for(int i=1,ans=1;i<1600;i++,ans++)
	{
		Addedge(S,i,1);Addedge(i+1600,T,1);
		for(int j=sqrt(i)+1;j*j<i*2&&j<=56;j++)
		  Addedge(j*j-i,i+1600,1);
		while(Bfs()) ans-=Dfs(S,0x7fffffff);
		if(ans>n) 
		  {printf("%d",i-1);return 0;}
	}
}

7 【COGS 729】[网络流24题] 圆桌聚餐

有m个单位，每个单位ri个人；有n张餐桌，每张餐桌可容纳ci个人。求就餐方案，使从同一个单位来的代表不在同一个餐桌就餐。

左边单位，和S相连，边权为ri；右边餐桌，和T相连，边权为ci；中间全部连起来，边权为1。
如果ans==∑ri，则存在方案，输出与每个单位连接的rest==0的餐桌即可 

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
#include<cstdio>
#include<queue>
using namespace std;
int n,m,S,T,ans,v,tot=1,ds[425],st[425],next[82000],to[82000],rest[82000];
queue<int> Q;
void Addedge(int x,int y,int z)
{
	to[++tot]=y;rest[tot]=z;next[tot]=st[x];st[x]=tot;
	to[++tot]=x;rest[tot]=0;next[tot]=st[y];st[y]=tot;
}
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 i=st[x];i;i=next[i])
		  if(rest[i]&&!ds[to[i]])
		    ds[to[i]]=ds[x]+1,Q.push(to[i]);
	}
	return ds[T];
}
int Dfs(int x,int flow)
{
	if(x==T) return flow;
	int a=0,b;
	for(int i=st[x];i;i=next[i])
	  if(rest[i]&&ds[to[i]]==ds[x]+1)
	  {
	  	b=Dfs(to[i],min(flow-a,rest[i]));
	  	rest[i]-=b;rest[i^1]+=b;a+=b;
	  	if(a==flow) break;
	  }
	if(!a) ds[x]=0;
	return a;
}
int main()
{
	freopen("roundtable.in","r",stdin);
	freopen("roundtable.out","w",stdout);
	scanf("%d%d",&m,&n);S=0;T=n+m+1;
	for(int i=1;i<=m;i++) 
	  scanf("%d",&v),Addedge(S,i,v),ans+=v;
	for(int i=1;i<=n;i++) 
	  scanf("%d",&v),Addedge(m+i,T,v);
	for(int i=1;i<=m;i++)
	  for(int j=n;j;j--)
	    Addedge(i,m+j,1);
	while(Bfs()) ans-=Dfs(S,0x7fffffff);
	if(ans) {printf("0\n");return 0;}
	printf("1\n");
	for(int i=1;i<=m;i++)
	{
		for(int j=st[i];j;j=next[j])
		  if(to[j]&&!rest[j]) printf("%d ",to[j]-m);
		printf("\n");
	}
}

8 【COGS 731】[网络流24题] 最长递增子序列

给定正整数序列x1,..., xn。
1 . 计算其最长递增子序列的长度s。
2 . 计算从给定的序列中最多（同时）可取出多少个长度为s的递增子序列。
3 . 如果允许在取出的序列中多次使用x1和xn，则从给定序列中最多（同时）可取出多少个长度为s的递增子序列。
ps：按照数据来说这题其实是最长不下降子序列

from byvoid:
【问题分析】
第一问是LIS，动态规划求解，第二问和第三问用网络最大流解决。
【建模方法】
首先动态规划求出F[i]，表示以第i位为开头的最长上升序列的长度，求出最长上升序列长度K。
1、把序列每位i拆成两个点< i.a >和< i.b >，从< i.a >到< i.b >连接一条容量为1的有向边。
2、建立附加源S和汇T，如果序列第i位有F[i]=K，从S到< i.a >连接一条容量为1的有向边。
3、如果F[i]=1，从< i.b >到T连接一条容量为1的有向边。
4、如果j > i且A[i] < A[j]且F[j]+1=F[i]，从< i.b >到< j.a >连接一条容量为1的有向边。
求网络最大流，就是第二问的结果。把边( < 1.a > , < 1.b > ) ( < N.a > , < N.b > ) ( S , < 1.a > ) ( < N.b > , T )这四条边的容量修改为无穷大，再求一次网络最大流，就是第三问结果。
【建模分析】
上述建模方法是应用了一种分层图的思想，把图每个顶点i按照F[i]的不同分为了若干层，这样图中从S出发到T的任何一条路径都是一个满足条件的最长上升子序列。由于序列中每个点要不可重复地取出，需要把每个点拆分成两个点。单位网络的最大流就是增广路的条数，所以最大流量就是第二问结果。第三问特殊地要求x1和xn可以重复使用，只需取消这两个点相关边的流量限制，求网络最大流即可。

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
#include<cstdio>
#include<queue>
using namespace std;
const int inf=1e7;
int n,m,S,T,ans,len,g[501],f[501];
int tot=1,ds[1005],st[1005],to[502005],rest[502005],next[502005];
queue<int> Q;
void Addedge(int x,int y,int z)
{
	to[++tot]=y;rest[tot]=z;next[tot]=st[x];st[x]=tot;
	to[++tot]=x;rest[tot]=0;next[tot]=st[y];st[y]=tot;
}
bool Bfs()
{
	for(int i=0;i<=T;i++) ds[i]=-1;
	Q.push(S);ds[S]=0;
	while(!Q.empty())
	{ 
		int x=Q.front();Q.pop();
		for(int i=st[x];i;i=next[i])
		  if(rest[i]&&ds[to[i]]==-1)
		    ds[to[i]]=ds[x]+1,Q.push(to[i]);
	}
	return ds[T]>-1;
}
int Dfs(int x,int flow)
{
 	if(x==T) return flow;
	int a=0,b;
	for(int i=st[x];i;i=next[i])
	  if(rest[i]&&ds[to[i]]==ds[x]+1)
	  {
	  	b=Dfs(to[i],min(flow-a,rest[i]));
	  	rest[i]-=b;rest[i^1]+=b;a+=b;
	  	if(a==flow) break;
	  }
	if(!a) ds[x]=-1;
	return a;
}
int main()
{
	freopen("alis.in","r",stdin);
	freopen("alis.out","w",stdout);
	scanf("%d",&n);S=0;T=n+n+1;
	for(int i=1;i<=n;i++) scanf("%d",&g[i]);
	for(int i=1;i<=n;i++)
	{
		f[i]=1;
		for(int j=1;j<i;j++)
		  if(g[j]<=g[i]&&f[i]<=f[j])
		    f[i]=f[j]+1;
		if(f[i]>len) len=f[i];
	}
	printf("%d\n",len);
	for(int i=1;i<=n;i++)
	{
		if(f[i]==1) Addedge(S,i,1);
		if(f[i]==len) Addedge(n+i,T,1);
		Addedge(i,n+i,1);
		for(int j=i+1;j<=n;j++)
	      if(g[j]>=g[i]&&f[i]+1==f[j]) 
		    Addedge(n+i,j,1);
	}
	while(Bfs()) ans+=Dfs(S,inf);
	printf("%d\n",ans);
	Addedge(1,n+1,inf);Addedge(n,n+n,inf);
	Addedge(S,1,inf);if(f[n]==len) Addedge(n+n,T,inf);
	while(Bfs()) ans+=Dfs(S,inf);
	printf("%d\n",ans);
}

9 【COGS 734】[网络流24题] 方格取数问题

在一个有m*n个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意2个数所在方格没有公共边，且取出的数的总和最大。

from:byvoid（不要问我这是啥，完全看不懂。。。）
【问题分析】
二分图点权最大独立集，转化为最小割模型，从而用最大流解决。
【建模方法】
首先把棋盘黑白染色，使相邻格子颜色不同，所有黑色格子看做二分图X集合中顶点，白色格子看做Y集合顶点，建立附加源S汇T。
1、从S向X集合中每个顶点连接一条容量为格子中数值的有向边。
2、从Y集合中每个顶点向T连接一条容量为格子中数值的有向边。
3、相邻黑白格子Xi,Yj之间从Xi向Yj连接一条容量为无穷大的有向边。
求出网络最大流，要求的结果就是所有格子中数值之和减去最大流量。
【建模分析】
这是一个二分图最大点权独立集问题，就是找出图中一些点，使得这些点之间没有边相连，这些点的权值之和最大。独立集与覆盖集是互补的，求最大点权独立集可以转化为求最小点权覆盖集（最小点权支配集）。最小点权覆盖集问题可以转化为最小割问题解决。结论:最大点权独立集 = 所有点权 - 最小点权覆盖集 = 所有点权 - 最小割集 = 所有点权 - 网络最大流。
对于一个网络，除去冗余点（不存在一条ST路径经过的点），每个顶点都在一个从S到T的路径上。割的性质就是不存在从S到T的路径，简单割可以认为割边关联的非ST节点为割点，而在二分图网络流模型中每个点必关联到一个割点（否则一定还有增广路，当前割不成立），所以一个割集对应了一个覆盖集（支配集）。最小点权覆盖集就是最小简单割，求最小简单割的建模方法就是把XY集合之间的变容量设为无穷大，此时的最小割就是最小简单割了。
有关二分图最大点权独立集问题，更多讨论见《最小割模型在信息学竞赛中的应用》作者胡伯涛。

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<cstdio>
#include<queue>
using namespace std;
const int inf=0x7fffffff;
int n,m,S,T,v,k,ans,tot=1,ds[905],st[905],to[5401],rest[5401],next[5401];
queue<int> Q;
void Addedge(int x,int y,int z)
{
	to[++tot]=y;rest[tot]=z;next[tot]=st[x];st[x]=tot;
	to[++tot]=x;rest[tot]=0;next[tot]=st[y];st[y]=tot;
}
bool Bfs()
{
	for(int i=0;i<=T;i++) ds[i]=-1;
	Q.push(S);ds[S]=0;
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();
		for(int i=st[x];i;i=next[i])
		  if(rest[i]&&ds[to[i]]==-1)
		    ds[to[i]]=ds[x]+1,Q.push(to[i]);
	}
	return ds[T]>-1;
}
int Dfs(int x,int flow)
{
	if(x==T) return flow;
	int a=0,b;
	for(int i=st[x];i;i=next[i])
	  if(rest[i]&&ds[to[i]]==ds[x]+1)
	  {
	  	b=Dfs(to[i],min(flow-a,rest[i]));
	  	rest[i]-=b;rest[i^1]+=b;a+=b;
	  	if(a==flow) break;
	  }
	if(!a) ds[x]=-1;
	return a;
}
int main()
{
	freopen("grid.in","r",stdin);
	freopen("grid.out","w",stdout);
	scanf("%d%d",&n,&m);S=0;T=n*m+1;
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++)
	  {
	  	scanf("%d",&v);k=(i-1)*m+j;ans+=v;
	  	if(!((i+j)%2)) 
		{
			Addedge(S,k,v);
			if(i!=1)  Addedge(k,k-m,inf);
			if(j!=1)  Addedge(k,k-1,inf);
		}  
		else 
		{
			Addedge(k,T,v);
			if(i!=1)  Addedge(k-m,k,inf);
			if(j!=1)  Addedge(k-1,k,inf);
		}  
	  }
	while(Bfs()) ans-=Dfs(S,inf);
	printf("%d\n",ans);
}

10 【COGS 461】[网络流24题] 餐巾

一个餐厅在相继的N天里，第i天需要Ri块餐巾(i=l，2，…，N)。餐厅可以从三种途径获得餐巾。
1 . 购买新的餐巾，每块需p分；
2 . 把用过的餐巾送到快洗部，洗一块需m天，费用需f分(f<p)。如m=l时，第一天送到快洗部的餐巾第二天就可以使用了，送慢洗的情况也如此。
3 . 把餐巾送到慢洗部，洗一块需n天(n>m)，费用需s分(s<f)。
在每天结束时，餐厅必须决定多少块用过的餐巾送到快洗部，多少块送慢洗部。在每天开始时，餐厅必须决定是否购买新餐巾及多少，使洗好的和新购的餐巾之和满足当天的需求量Ri，并使N天总的费用最小。

把每天分为二分图两个集合中的顶点Xi,Yi，建立附加源S汇T。
1、从S向每个Xi连一条容量为ri，费用为0的有向边。
2、从每个Yi向T连一条容量为ri，费用为0的有向边。
3、从S向每个Yi连一条容量为无穷大，费用为p的有向边。
4、从每个Xi向Xi+1(i+1<=N)连一条容量为无穷大，费用为0的有向边。
5、从每个Xi向Yi+m(i+m<=N)连一条容量为无穷大，费用为f的有向边。
6、从每个Xi向Yi+n(i+n<=N)连一条容量为无穷大，费用为s的有向边。

经过分析可以把每天要用的和用完的分离开处理，建模后就是二分图。二分图X集合中顶点Xi表示第i天用完的餐巾，其数量为ri，所以从S向Xi连接容量为ri的边作为限制。Y集合中每个点Yi则是第i天需要的餐巾，数量为ri，与T连接的边容量作为限制。每天用完的餐巾可以选择留到下一天（Xi->Xi+1），不需要花费，送到快洗部(Xi->Yi+m)，费用为f，送到慢洗部(Xi->Yi+n)，费用为s。每天需要的餐巾除了刚刚洗好的餐巾，还可能是新购买的(S->Yi)，费用为p。

解法2：
将每一天拆成两个点i, i’，加如下6条边：
(s, i, ri, p)——在第i天可以买至多ri个餐巾，每块p分；
(i, t, ri, 0)——第i天要用ri块餐巾；
(s, i’, ri, 0)——第i天用剩的ri块旧餐巾；
(i’, i+m, ∞, f)——第i天的旧餐巾送到快洗部，每块f分；
(i’, i+n, ∞, s)——第i天的旧餐巾送到慢洗部，每块s分；
(i’, i’+1, ∞, 0)——第i天的旧餐巾可以留到第i+1天再处理；
好像比上一个好理解一些 

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
#include<cstdio>
#include<queue>
using namespace std;
const int inf=0x3fffffff;
int N,p,m,f,n,s,S,T,ds[405],pre[405],maxflow,mincost;
int ecnt=1,st[405],to[2400],rest[2400],cost[2400],next[2400];
bool used[405];
queue<int> Q;
void Addedge(int x,int y,int r,int c)
{
	to[++ecnt]=y;rest[ecnt]=r;cost[ecnt]=c;next[ecnt]=st[x];st[x]=ecnt;
	to[++ecnt]=x;rest[ecnt]=0;cost[ecnt]=-c;next[ecnt]=st[y];st[y]=ecnt;
}
bool Spfa()
{
	for(int i=0;i<=T;i++) ds[i]=inf,used[i]=0;
	Q.push(S);ds[S]=0;used[S]=1;
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();used[x]=0;
		for(int e=st[x],y=to[e];e;e=next[e],y=to[e])
		  if(rest[e]&&ds[y]>ds[x]+cost[e])
		  {
		  	ds[y]=ds[x]+cost[e];
		  	pre[y]=e;
		  	if(!used[y]) used[y]=1,Q.push(y); 
		  }
	}
	return ds[T]<inf;
}
void Update(int flow)
{
	for(int e=pre[T];e;e=pre[to[e^1]])
	  flow=min(flow,rest[e]);
	for(int e=pre[T];e;e=pre[to[e^1]])
	  rest[e]-=flow,rest[e^1]+=flow;
	mincost+=flow*ds[T];
}
int main()
{
	freopen("napkin.in","r",stdin);
	freopen("napkin.out","w",stdout);
	scanf("%d",&N);S=0;T=N+N+1;
	for(int i=1,v;i<=N;i++)
	  scanf("%d",&v),Addedge(S,i,v,0),Addedge(N+i,T,v,0);
	scanf("%d%d%d%d%d",&p,&m,&f,&n,&s);
	for(int i=1;i<=N;i++)
	{
		Addedge(S,N+i,inf,p);
		if(i<N)    Addedge(i,i+1,inf,0);
		if(i+m<=N) Addedge(i,i+m+N,inf,f);
		if(i+n<=N) Addedge(i,i+n+N,inf,s);
	}
	while(Spfa()) Update(inf);
	printf("%d",mincost);
}

11 【SGU 194】Reactor Cooling

给n个点，m根pipe，每根pipe是用来流躺液体的，单向的，每时每刻每根pipe流进来的物质要等于流出去的物质。要使得m条pipe组成一个循环体，里面流躺物质，并且满足每根pipe一定的流量限制，范围为[Li,Ri]，即要满足每时刻流进来的不能超过Ri(最大流问题)，同时最小不能低于Li。

建图模型：
以前写的最大流默认的下界为0，而这里的下界却不为0，所以我们要进行再构造让每条边的下界为0，这样做是为了方便处理。对于每根管子有一个上界容量high和一个下界容量low，我们让这根管子的容量下界变为0，上界为high-low。可是这样做了的话流量就不守恒了，为了再次满足流量守恒，即每个节点"入流=出流"，我们增设一个超级源点S和一个超级终点T。我们开设一个数组in[]来记录每个节点的流量情况。

in[i]=∑in[i]（i节点所有入流下界之和）- ∑out[i]（i节点所有出流下界之和）。
当in[i]大于0的时候，S到i连一条流量为in[i]的边。
当in[i]小于0的时候，i到T连一条流量为-in[i]的边。
最后对（S,T）求一次最大流即可，当所有附加边全部满流时（即maxflow==\(\sum\limits_{in[i]>0}in[i]\)），有可行解。

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
#include<cstdio>
#include<queue>
using namespace std;
const int inf=0x3fffffff;
int n,m,S,T,ans,u,v,low[20000],high,in[205];
int tot=1,ds[205],st[205],to[41000],rest[41000],next[41000];
queue<int> Q;
void Addedge(int x,int y,int z)
{
	to[++tot]=y;rest[tot]=z;next[tot]=st[x];st[x]=tot;
	to[++tot]=x;rest[tot]=0;next[tot]=st[y];st[y]=tot;
}
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 i=st[x];i;i=next[i])
		  if(rest[i]&&!ds[to[i]])
		    ds[to[i]]=ds[x]+1,Q.push(to[i]);
	}
	return ds[T];
}
int Dfs(int x,int flow)
{
	if(x==T) return flow;
	int a=0,b;
	for(int i=st[x];i;i=next[i])
	  if(rest[i]&&ds[to[i]]==ds[x]+1)
	  {
	  	b=Dfs(to[i],min(flow-a,rest[i]));
	  	rest[i]-=b;rest[i^1]+=b;a+=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;i<=m;i++)
	{
		scanf("%d%d%d%d",&u,&v,&low[i],&high);
		Addedge(u,v,high-low[i]);
		in[u]-=low[i];in[v]+=low[i];
	}
	for(int i=1;i<=n;i++)
	{
		if(in[i]>=0) Addedge(S,i,in[i]),ans+=in[i];
		else Addedge(i,T,-in[i]);
	}
	while(Bfs()) ans-=Dfs(S,inf);
	if(ans) { printf("NO\n");return 0; }
	printf("YES\n");
	for(int i=1;i<=m;i++)
	  printf("%d\n",rest[i*2+1]+low[i]);
}
网络流