网络流

  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]);
}