【解题报告】网络流24题

83 阅读 0 评论 55 点赞

我是靠谱客的博主幸福野狼，最近开发中收集的这篇文章主要介绍【解题报告】网络流24题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1.飞行员配对方案问题

链接：「网络流 24 题」搭配飞行员

题意：每架飞机需要两个驾驶员，一个正驾驶员和一个副驾驶员。由于种种原因，有些驾驶员不能在同一架飞机上飞行，问如何搭配驾驶员才能使出航的飞机最多。两个正驾驶员或两个副驾驶员都不能同机飞行。

分析：二分图最大匹配裸题。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #define LL long long
 5 using namespace std;
 6 const int N=105;
 7 const int inf=0x3f3f3f3f;
 8 int n,m,x,y,S,T,cnt=1,ans;
 9 int cur[N],first[N],dis[N],q[N];
10 struct edge{int to,next,flow;}e[N*N*4];
11 int read()
12 {
13     int x=0,f=1;char c=getchar();
14     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
15     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
16     return x*f;
17 }
18 void insert(int u,int v,int w)
19 {
20     e[++cnt]=(edge){v,first[u],w};first[u]=cnt;
21     e[++cnt]=(edge){u,first[v],0};first[v]=cnt;
22 }
23 bool bfs()
24 {
25     memset(dis,-1,sizeof(dis));
26     int head=0,tail=1;
27     q[head]=S;dis[S]=0;
28     while(head!=tail)
29     {
30         int u=q[head++];
31         for(int i=first[u];i;i=e[i].next)
32         {
33             int v=e[i].to;
34             if(dis[v]!=-1||!e[i].flow)continue;
35             dis[v]=dis[u]+1;
36             q[tail++]=v;
37         }
38     }
39     return dis[T]!=-1;
40 }
41 int dfs(int u,int a)
42 {
43     if(u==T||a==0)return a;
44     int f,flow=0;
45     for(int& i=cur[u];i;i=e[i].next)
46     {
47         int v=e[i].to;
48         if(dis[v]==dis[u]+1&&(f=dfs(v,min(e[i].flow,a)))>0)
49         {
50             e[i].flow-=f;e[i^1].flow+=f;
51             flow+=f;a-=f;if(a==0)break;
52         }
53     }
54     return flow;
55 }
56 int main()
57 {
58     n=read();m=read();S=0;T=n+1;
59     while(scanf("%d%d",&x,&y)==2)insert(x,y,1);
60     for(int i=1;i<=m;i++)insert(S,i,1);
61     for(int i=m+1;i<=n;i++)insert(i,T,1);
62     while(bfs())
63     {
64         for(int i=S;i<=T;i++)cur[i]=first[i];
65         ans+=dfs(S,inf);
66     }
67     printf("%dn",ans);
68     return 0;
69 }

View Code

2.太空飞行计划问题

链接：「网络流 24 题」太空飞行计划

题意：现已确定了一个可供选择的实验集合 $E = { E_1, E_2, cdots, E_m }$，和进行这些实验需要使用的全部仪器的集合 $I = { I_1, I_2, cdots, I_n }$。实验 $E_j$ 需要用到的仪器是 $I$ 的子集 $R_j subseteq I$。配置仪器 $I_k$ 的费用为 $c_k$ 美元。实验 $E_j$ 的赞助商已同意为该实验结果支付 $p_j$ 美元。对于给定的实验和仪器配置情况，找出净收益最大的试验计划。

分析：最大权闭合子图。从 $S$ 向每个实验连一条容量为 $p_i$ 的边，每个实验向所需要的仪器连一条容量为 $inf$ 的边，每个仪器向 $T$ 连一条容量为 $c_i$ 的边。答案为 $sum p_i-maxflow$ 。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #define LL long long
 5 using namespace std;
 6 const int N=105;
 7 const int inf=0x3f3f3f3f;
 8 int n,m,x,S,T,cnt=1,ans,sum,num;
 9 int cur[N],first[N],dis[N],q[N];
10 bool vis[N];
11 char c;
12 struct edge{int to,next,flow;}e[N*N*2];
13 int read()
14 {
15     int x=0,f=1;char c=getchar();
16     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
17     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
18     return x*f;
19 }
20 void insert(int u,int v,int w)
21 {
22     e[++cnt]=(edge){v,first[u],w};first[u]=cnt;
23     e[++cnt]=(edge){u,first[v],0};first[v]=cnt;
24 }
25 bool bfs()
26 {
27     memset(dis,-1,sizeof(dis));
28     int head=0,tail=1;
29     q[head]=S;dis[S]=0;
30     while(head!=tail)
31     {
32         int u=q[head++];
33         for(int i=first[u];i;i=e[i].next)
34         {
35             int v=e[i].to;
36             if(dis[v]!=-1||!e[i].flow)continue;
37             dis[v]=dis[u]+1;
38             q[tail++]=v;
39         }
40     }
41     return dis[T]!=-1;
42 }
43 int dfs(int u,int a)
44 {
45     if(u==T||a==0)return a;
46     int f,flow=0;
47     for(int& i=cur[u];i;i=e[i].next)
48     {
49         int v=e[i].to;
50         if(dis[v]==dis[u]+1&&(f=dfs(v,min(e[i].flow,a)))>0)
51         {
52             e[i].flow-=f;e[i^1].flow+=f;
53             flow+=f;a-=f;if(a==0)break;
54         }
55     }
56     return flow;
57 }
58 void find(int x)
59 {
60     vis[x]=true;
61     for(int i=first[x];i;i=e[i].next)
62         if(!vis[e[i].to]&&e[i].flow)
63             find(e[i].to);
64 }
65 int main()
66 {
67     n=read();m=read();S=0;T=n+m+1;
68     for(int i=1;i<=n;i++)
69     {
70         x=read();sum+=x;insert(S,i,x);
71         while(1)
72         {
73             num=0;c=getchar();
74             while(c<'0'||c>'9')c=getchar();
75             while(c>='0'&&c<='9')num=num*10+c-'0',c=getchar();
76             insert(i,num+n,inf);
77             if(c=='r')break;
78         }
79     }
80     for(int i=1;i<=m;i++)x=read(),insert(i+n,T,x);
81     while(bfs())
82     {
83         for(int i=S;i<=T;i++)cur[i]=first[i];
84         ans+=dfs(S,inf);
85     }
86     find(S);
87     for(int i=1;i<=n;i++)if(vis[i])printf("%d ",i);
88     printf("n");
89     for(int i=n+1;i<=n+m;i++)if(vis[i])printf("%d ",i-n);
90     printf("n");
91     printf("%dn",sum-ans);
92     return 0;
93 }

View Code

3.最小路径覆盖问题

链接：「网络流 24 题」最小路径覆盖

题意：给定有向图 $G = (V, E)$。设 $P$ 是 $G$ 的一个简单路（顶点不相交）的集合。如果 $V$ 中每个顶点恰好在 $P$ 的一条路上，则称 $P$ 是 $G$ 的一个路径覆盖。 $P$ 中路径可以从 $V$ 的任何一个顶点开始，长度也是任意的，特别地，可以为 $0$。$G$ 的最小路径覆盖是 $G$ 的所含路径条数最少的路径覆盖。求一个有向无环图 $G$ 的最小路径覆盖。

分析：二分图最大匹配。将每个点拆为两个点，在新图中对应连边。二分图的每一个合法匹配都可以视为一种路径覆盖的方式，路径条数为总点数-匹配数。最小不相交路径覆盖即为总点数-二分图最大匹配。（建图方式仅限DAG）

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #define LL long long
 5 using namespace std;
 6 const int N=405;
 7 const int inf=0x3f3f3f3f;
 8 int n,m,x,y,S,T,cnt=1,ans;
 9 int cur[N],first[N],dis[N],q[N],ind[N],to[N];
10 struct edge{int to,next,flow;}e[N*N*2];
11 int read()
12 {
13     int x=0,f=1;char c=getchar();
14     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
15     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
16     return x*f;
17 }
18 void insert(int u,int v,int w)
19 {
20     e[++cnt]=(edge){v,first[u],w};first[u]=cnt;
21     e[++cnt]=(edge){u,first[v],0};first[v]=cnt;
22 }
23 bool bfs()
24 {
25     memset(dis,-1,sizeof(dis));
26     int head=0,tail=1;
27     q[head]=S;dis[S]=0;
28     while(head!=tail)
29     {
30         int u=q[head++];
31         for(int i=first[u];i;i=e[i].next)
32         {
33             int v=e[i].to;
34             if(dis[v]!=-1||!e[i].flow)continue;
35             dis[v]=dis[u]+1;
36             q[tail++]=v;
37         }
38     }
39     return dis[T]!=-1;
40 }
41 int dfs(int u,int a)
42 {
43     if(u==T||a==0)return a;
44     int f,flow=0;
45     for(int& i=cur[u];i;i=e[i].next)
46     {
47         int v=e[i].to;
48         if(dis[v]==dis[u]+1&&(f=dfs(v,min(e[i].flow,a)))>0)
49         {
50             e[i].flow-=f;e[i^1].flow+=f;
51             flow+=f;a-=f;if(a==0)break;
52         }
53     }
54     return flow;
55 }
56 int main()
57 {
58     n=read();m=read();S=0;T=n*2+1;
59     for(int i=1;i<=m;i++)
60     {
61         x=read();y=read();
62         insert(x,y+n,1);
63     }
64     for(int i=1;i<=n;i++)insert(S,i,1);
65     for(int i=1;i<=n;i++)insert(i+n,T,1);
66     while(bfs())
67     {
68         for(int i=S;i<=T;i++)cur[i]=first[i];
69         ans+=dfs(S,inf);
70     }
71     for(int x=1;x<=n;x++)
72         for(int i=first[x];i;i=e[i].next)
73             if(!e[i].flow&&e[i].to)to[x]=e[i].to-n,ind[e[i].to-n]++;
74     for(int x=1;x<=n;x++)
75         if(!ind[x])
76         {
77             for(int i=x;i;i=to[i])printf("%d ",i);
78             printf("n");
79         }
80     printf("%dn",n-ans);
81     return 0;
82 }

View Code

4.魔术球问题

链接：「网络流 24 题」魔术球

题意：假设有 $n$ 根柱子，按下述规则在这 $n$ 根柱子中依次放入编号为 $1, 2, 3, 4, cdots$ 的球：每次只能在某根柱子的最上面放球；在同一根柱子中，任何 $2$ 个相邻球的编号之和为完全平方数。试计算出在 $n$ 根柱子上最多能放多少个球。

分析：二分图最大匹配。题目限制了在放置好每个 $x$ 之前，需先放置好 $1,2,3,cdots x-1$ 的球。考虑枚举答案 $x$ ，建立关于 $1,2,3,cdots x$ 的图：若 $i<j$ 且 $i+j$ 为完全平方数，则连接边 $(i,j)$。原图是一个DAG，问题转化为求DAG的最小不相交路径覆盖。按顺序枚举 $x$ ，当最小路径覆盖数大于 $n$ 时结束。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cmath>
 5 #define LL long long
 6 using namespace std;
 7 const int N=1e4+5;
 8 const int base=5e3;
 9 const int inf=0x3f3f3f3f;
10 int n,m,x,y,S,T,cnt=1,ans,sum;
11 int cur[N],first[N],dis[N],q[N],to[N];
12 bool vis[N];
13 struct edge{int to,next,flow;}e[N*20];
14 int read()
15 {
16     int x=0,f=1;char c=getchar();
17     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
18     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
19     return x*f;
20 }
21 void insert(int u,int v,int w)
22 {
23     e[++cnt]=(edge){v,first[u],w};first[u]=cnt;
24     e[++cnt]=(edge){u,first[v],0};first[v]=cnt;
25 }
26 bool bfs()
27 {
28     memset(dis,-1,sizeof(dis));
29     int head=0,tail=1;
30     q[head]=S;dis[S]=0;
31     while(head!=tail)
32     {
33         int u=q[head++];
34         for(int i=first[u];i;i=e[i].next)
35         {
36             int v=e[i].to;
37             if(dis[v]!=-1||!e[i].flow)continue;
38             dis[v]=dis[u]+1;
39             q[tail++]=v;
40         }
41     }
42     return dis[T]!=-1;
43 }
44 int dfs(int u,int a)
45 {
46     if(u==T||a==0)return a;
47     int f,flow=0;
48     for(int& i=cur[u];i;i=e[i].next)
49     {
50         int v=e[i].to;
51         if(dis[v]==dis[u]+1&&(f=dfs(v,min(e[i].flow,a)))>0)
52         {
53             e[i].flow-=f;e[i^1].flow+=f;
54             flow+=f;a-=f;if(a==0)break;
55         }
56     }
57     return flow;
58 }
59 bool ok(int x)
60 {
61     int t=(int)(sqrt(x)+1e-9);
62     return t*t==x;
63 }
64 int main()
65 {
66     n=read();S=0;T=base*2+1;
67     while(1)
68     {
69         ans++;sum++;
70         for(int i=1;i<ans;i++)
71             if(ok(i+ans))insert(i,ans+base,1);
72         insert(S,ans,1);insert(ans+base,T,1);
73         while(bfs())
74         {
75             for(int i=S;i<=T;i++)cur[i]=first[i];
76             sum-=dfs(S,inf);
77         }
78         if(sum>n)break;
79     }
80     ans--;printf("%dn",ans);
81     for(int x=1;x<=ans;x++)
82         for(int i=first[x];i;i=e[i].next)
83             if(!e[i].flow&&e[i].to)
84                 {to[x]=e[i].to-base;break;}
85     for(int x=1;x<=ans;x++)
86         if(!vis[x])
87         {
88             for(int i=x;i;i=to[i])
89                 printf("%d ",i),vis[i]=true;
90             printf("n");
91         }
92     return 0;
93 }

View Code

5.圆桌问题

链接：「网络流 24 题」圆桌聚餐

题意：假设有来自 $n$ 个不同单位的代表参加一次国际会议。每个单位的代表数分别为 $r_i$ 。会议餐厅共有 $m$ 张餐桌，每张餐桌可容纳 $c_i$ 个代表就餐。为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。试给出满足要求的代表就餐方案。

分析：最大流。从 $S$ 向每个单位连一条容量为人数的边，从餐桌向 $T$ 连接一条容量为餐桌容量的边，从单位向每个餐桌连一条容量为 $1$ 的边。直接跑最大流求解。（或者是贪心+线段树，餐桌和人数都从大到小排序，每次安排时按餐桌剩余容量从大到小安排。为维护单调性，对于最后一段相等的区间，需要减线段树上靠后的部分。）

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cmath>
 5 #define LL long long
 6 using namespace std;
 7 const int N=505;
 8 const int inf=0x3f3f3f3f;
 9 int n,m,x,S,T,cnt=1,ans,sum;
10 int cur[N],first[N],dis[N],q[N];
11 struct edge{int to,next,flow;}e[N*N*2];
12 int read()
13 {
14     int x=0,f=1;char c=getchar();
15     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
16     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
17     return x*f;
18 }
19 void insert(int u,int v,int w)
20 {
21     e[++cnt]=(edge){v,first[u],w};first[u]=cnt;
22     e[++cnt]=(edge){u,first[v],0};first[v]=cnt;
23 }
24 bool bfs()
25 {
26     memset(dis,-1,sizeof(dis));
27     int head=0,tail=1;
28     q[head]=S;dis[S]=0;
29     while(head!=tail)
30     {
31         int u=q[head++];
32         for(int i=first[u];i;i=e[i].next)
33         {
34             int v=e[i].to;
35             if(dis[v]!=-1||!e[i].flow)continue;
36             dis[v]=dis[u]+1;
37             q[tail++]=v;
38         }
39     }
40     return dis[T]!=-1;
41 }
42 int dfs(int u,int a)
43 {
44     if(u==T||a==0)return a;
45     int f,flow=0;
46     for(int& i=cur[u];i;i=e[i].next)
47     {
48         int v=e[i].to;
49         if(dis[v]==dis[u]+1&&(f=dfs(v,min(e[i].flow,a)))>0)
50         {
51             e[i].flow-=f;e[i^1].flow+=f;
52             flow+=f;a-=f;if(a==0)break;
53         }
54     }
55     return flow;
56 }
57 int main()
58 {
59     n=read();m=read();S=0;T=n+m+1;
60     for(int i=1;i<=n;i++)x=read(),sum+=x,insert(S,i,x);
61     for(int i=1;i<=m;i++)x=read(),insert(i+n,T,x);
62     for(int i=1;i<=n;i++)
63         for(int j=1;j<=m;j++)
64             insert(i,j+n,1);
65     while(bfs())
66     {
67         for(int i=S;i<=T;i++)cur[i]=first[i];
68         ans+=dfs(S,inf);
69     }
70     if(ans<sum){printf("0n");return 0;}
71     printf("1n");
72     for(int i=1;i<=n;i++,printf("n"))
73         for(int j=first[i];j;j=e[j].next)
74             if(!e[j].flow&&e[j].to)printf("%d ",e[j].to-n);
75     return 0;
76 }

View Code

6.最长递增子序列问题

链接：「网络流 24 题」最长递增子序列

题意：给定正整数序列 $x_1 sim x_n$ ，以下递增均为非严格递增。计算其最长递增子序列的长度 $s$。计算从给定的序列中最多可取出多少个长度为 $s$ 的递增子序列。如果允许在取出的序列中多次使用 $x_1$ 和 $x_n$ ，则从给定序列中最多可取出多少个长度为 $s$ 的递增子序列。

分析：令 $f_i$ 表示以第 $i$ 位开头的最长递增子序列长度，可用dp求解。若 $f_i=s$ ，则从 $S$ 向 $i$ 连一条容量为 $1$ 的边；若 $f_i=1$ ，则从 $i$ 向 $T$ 连一条容量为 $1$ 的边；限定每个点只选一次，拆点，连一条容量为 $1$ 的边；若 $i<j$ 且 $x_i<=x_j$ 且 $f_i=f_j+1$ ，则从 $i$ 向 $j$ 连一条容量为 $1$ 的边。直接跑最大流求解即可。回答第三问时，把对应边的限制放成 $inf$ ，再跑一次最大流。

  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<cmath>
  5 #define LL long long
  6 using namespace std;
  7 const int N=1005;
  8 const int inf=0x3f3f3f3f;
  9 int S,T,cnt=1,ans;
 10 int cur[N],first[N],dis[N],q[N];
 11 int n,length,x[N],f[N];
 12 struct edge{int to,next,flow;}e[N*N*2];
 13 int read()
 14 {
 15     int x=0,f=1;char c=getchar();
 16     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
 17     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
 18     return x*f;
 19 }
 20 void insert(int u,int v,int w)
 21 {
 22     e[++cnt]=(edge){v,first[u],w};first[u]=cnt;
 23     e[++cnt]=(edge){u,first[v],0};first[v]=cnt;
 24 }
 25 bool bfs()
 26 {
 27     memset(dis,-1,sizeof(dis));
 28     int head=0,tail=1;
 29     q[head]=S;dis[S]=0;
 30     while(head!=tail)
 31     {
 32         int u=q[head++];
 33         for(int i=first[u];i;i=e[i].next)
 34         {
 35             int v=e[i].to;
 36             if(dis[v]!=-1||!e[i].flow)continue;
 37             dis[v]=dis[u]+1;
 38             q[tail++]=v;
 39         }
 40     }
 41     return dis[T]!=-1;
 42 }
 43 int dfs(int u,int a)
 44 {
 45     if(u==T||a==0)return a;
 46     int f,flow=0;
 47     for(int& i=cur[u];i;i=e[i].next)
 48     {
 49         int v=e[i].to;
 50         if(dis[v]==dis[u]+1&&(f=dfs(v,min(e[i].flow,a)))>0)
 51         {
 52             e[i].flow-=f;e[i^1].flow+=f;
 53             flow+=f;a-=f;if(a==0)break;
 54         }
 55     }
 56     return flow;
 57 }
 58 int main()
 59 {
 60     n=read();S=0;T=n*2+1;
 61     for(int i=1;i<=n;i++)x[i]=read(),f[i]=1;
 62     for(int i=n;i>=1;i--)
 63     {
 64         for(int j=n;j>i;j--)
 65             if(x[j]>=x[i])f[i]=max(f[i],f[j]+1);
 66         length=max(length,f[i]);
 67     }
 68     printf("%dn",length);
 69     if(length==1){printf("%dn%dn",n,n);return 0;}
 70     for(int i=1;i<=n;i++)insert(i,i+n,1);
 71     for(int i=1;i<=n;i++)
 72     {
 73         if(f[i]==length)insert(S,i,1);
 74         if(f[i]==1)insert(i+n,T,1);
 75         for(int j=i+1;j<=n;j++)
 76             if(x[i]<=x[j]&&f[i]==f[j]+1)insert(i+n,j,1);
 77     }
 78     while(bfs())
 79     {
 80         for(int i=S;i<=T;i++)cur[i]=first[i];
 81         ans+=dfs(S,inf);
 82     }
 83     printf("%dn",ans);
 84     ans=0;cnt=1;
 85     memset(first,0,sizeof(first));
 86     insert(1,1+n,inf);insert(n,n+n,inf);
 87     for(int i=2;i<n;i++)insert(i,i+n,1);
 88     for(int i=1;i<=n;i++)
 89     {
 90         if(f[i]==length)
 91         {
 92             if(i==1||i==n)insert(S,i,inf);
 93             else insert(S,i,1);
 94         }
 95         if(f[i]==1)
 96         {
 97             if(i==1||i==n)insert(i+n,T,inf);
 98             else insert(i+n,T,1);
 99         }
100         for(int j=i+1;j<=n;j++)
101             if(x[i]<=x[j]&&f[i]==f[j]+1)insert(i+n,j,1);
102     }
103     while(bfs())
104     {
105         for(int i=S;i<=T;i++)cur[i]=first[i];
106         ans+=dfs(S,inf);
107     }
108     printf("%dn",ans);
109     return 0;
110 }

View Code

7.试题库问题

链接：「网络流 24 题」试题库

题意：假设一个试题库中有 $n$ 道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取 $m$ 道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算法。

分析：最大流。从 $S$ 向每种类别连一条容量为需求的边，从题目向 $T$ 连接一条容量为 $1$ 的边，从每个类别向题目连一条容量为 $1$ 的边。直接跑最大流求解即可。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 using namespace std;
 5 const int N=1200;
 6 const int inf=0x3f3f3f3f;
 7 int n,m,sum,p,x,S,T,cnt=1,ans;
 8 int first[N],cur[N],q[N],dis[N];
 9 struct edge{int to,next,flow;}e[N*40];
10 int read()
11 {
12     int x=0,f=1;char c=getchar();
13     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
14     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
15     return x*f;
16 }
17 void insert(int u,int v,int w)
18 {
19     e[++cnt]=(edge){v,first[u],w};first[u]=cnt;
20     e[++cnt]=(edge){u,first[v],0};first[v]=cnt;
21 }
22 bool bfs()
23 {
24     memset(dis,-1,sizeof(dis));
25     int head=0,tail=1;
26     q[head]=S;dis[S]=0;
27     while(head!=tail)
28     {
29         int u=q[head++];
30         for(int i=first[u];i;i=e[i].next)
31         {
32             int v=e[i].to;
33             if(dis[v]!=-1||!e[i].flow)continue;
34             dis[v]=dis[u]+1;
35             q[tail++]=v;
36         }
37     }
38     return dis[T]!=-1;
39 }
40 int dfs(int u,int a)
41 {
42     if(u==T||a==0)return a;
43     int f,flow=0;
44     for(int& i=cur[u];i;i=e[i].next)
45     {
46         int v=e[i].to;
47         if(dis[v]==dis[u]+1&&(f=dfs(v,min(e[i].flow,a)))>0)
48         {
49             e[i].flow-=f;e[i^1].flow+=f;
50             flow+=f;a-=f;if(a==0)break;
51         }
52     }
53     return flow;
54 }
55 int main()
56 {
57     n=read();m=read();S=0;T=n+m+1;
58     for(int i=1;i<=n;i++)x=read(),sum+=x,insert(S,i,x);
59     for(int i=1;i<=m;i++)
60     {
61         p=read();
62         while(p--)x=read(),insert(x,i+n,1);
63     }
64     for(int i=1;i<=m;i++)insert(i+n,T,1);
65     while(bfs())
66     {
67         for(int i=S;i<=T;i++)cur[i]=first[i];
68         ans+=dfs(S,inf);
69     }
70     if(ans<sum){printf("No Solution!n");return 0;}
71     for(int x=1;x<=n;x++,printf("n"))
72     {
73         printf("%d: ",x);
74         for(int i=first[x];i;i=e[i].next)
75         {
76             int to=e[i].to;
77             if(!to||e[i].flow)continue;
78             printf("%d ",to-n);
79         }
80     }
81     return 0;
82 }

View Code

8.机器人路径规划问题

链接：PowerOJ1743: 机器人路径规划问题

题意：给定树状路径上的起点 $s$ 和终点 $t$，机器人要从 $s$ 运动到 $t$ 。树状路径上有若干可移动的障碍物。由于路径狭窄，任何时刻在路径的任何位置不能同时容纳 $2$ 个物体。每一步可以将障碍物或机器人移到相邻的空顶点上。设计一个有效算法用最少移动次数使机器人从 $s$ 运动到 $t$。编程任务：对于给定的树，以及障碍物在树中的分布情况，计算机器人的最少移动次数。

分析：网络流的复杂度是 $O(n^9)$ 的，ImmortalCO给出了一种 $O(n^6)$ 的动态规划解法。参考《机器人路径规划问题(TMP1R)题解》。

9.方格取数问题

链接：「网络流 24 题」方格取数

题意：在一个有 $m times n$ 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意 $2$ 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。

分析：最大点权独立集。先将棋盘黑白染色，从 $S$ 向每个黑点连一条容量为黑点数值的边，从白点向 $T$ 连接一条容量为白点数值的边，从每个黑点向白点连一条容量为 $inf$ 的边。答案为总价值-最小割。

10.餐巾计划问题

链接：「网络流 24 题」餐巾计划

题意：一个餐厅在相继的 $n$ 天里，每天需用的餐巾数不尽相同。假设第 $i$ 天需要 $r_i$ 块餐巾。餐厅可以购买新的餐巾，每块餐巾的费用为 $P$ 分；或者把旧餐巾送到快洗部，洗一块需 $M$ 天，其费用为 $F$ 分；或者送到慢洗部，洗一块需 $N$ 天，其费用为 $S$ 分（$S < F$）。每天结束时，餐厅必须决定将多少块脏的餐巾送到快洗部，多少块餐巾送到慢洗部，以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和，要满足当天的需求量。试设计一个算法为餐厅合理地安排好 $n$ 天中餐巾使用计划,使总的花费最小。

分析：把每一天都拆成一对点 $x_i$ 和 $y_i$ ，$x_i$ 表示脏的餐巾，$y_i$ 表示干净的餐巾。从 $S$ 向 $y_i$ 连一条容量为 $inf$ 费用为 $P$ 的边，代表购买决策；从 $y_i$ 向 $T$ 连一条容量为 $r_i$ 费用为 $0$ 的边，代表每天需求；从 $S$ 向 $x_i$ 连一条容量为 $r_i$ 费用为 $0$ 的边，代表每天剩余的未洗餐巾；从 $x_i$ 向 $x_i+1$ 连一条容量为 $inf$ 费用为 $0$ 的边，代表将脏餐巾屯到下一天；从 $x_i$ 向 $y_i+m$ 连一条容量为 $inf$ 费用为 $F$ 的边，代表快洗决策；从 $x_i$ 向 $y_i+n$ 连一条容量为 $inf$ 费用为 $S$ 的边，代表慢洗决策。直接跑最小费用最大流即可。

11.航空路线问题

链接：「网络流 24 题」航空路线问题

题意：给定一张航空图，图中顶点代表城市，边代表两个城市间的直通航线。现要求找出一条满足下述限制条件的且途经城市最多的旅行路线：从最西端城市出发，单向从西向东途经若干城市到达最东端城市，然后再单向从东向西飞回起点（可途经若干城市）；除起点城市外，任何城市只能访问一次。对于给定的航空图，试设计一个算法找出一条满足要求的最佳航空旅行路线。

分析：问题转化为求两条不相交的路径且路径之和最长。考虑拆点，连一条容量为 $1$ 费用为 $-1$ 的边（$1$ 和 $n$ 的容量为 $2$ ）。跑最小费用最大流求解，若最大流不等于 $2$ 则无解。

12.软件补丁问题

链接：「网络流 24 题」软件补丁

题意：某公司发现其研制的一个软件中有 $n$ 个错误，随即为该软件发放了一批共 $m$ 个补丁程序。对于每一个补丁 $i$ ，都有 $2$ 个与之相应的错误集合 $B_1(i)$ 和 $B_2(i)$ ，使得仅当软件包含 $B_1(i)$ 中的所有错误，而不包含 $B_2(i)$ 中的任何错误时，才可以使用补丁 $i$。补丁 $i$ 将修复软件中的某些错误 $F_1(i)$ ，而同时加入另一些错误 $F_2(i)$。另外，每个补丁都耗费一定的时间。试设计一个算法，利用公司提供的 $m$ 个补丁程序将原软件修复成一个没有错误的软件，并使修复后的软件耗时最少。

分析：将bug状态压成二进制之后跑最短路。

13.星际转移问题

链接：「网络流 24 题」星际转移

题意：现有 $n$ 个太空站位于地球与月球之间，且有 $m$ 艘公共交通太空船在其间来回穿梭。每个太空站可容纳无限多的人，而每艘太空船 $i$ 只可容纳 $H_i$ 个人。每艘太空船将周期性地停靠一系列的太空站，例如：$1,3,4$ 表示该太空船将周期性地停靠太空站 $134134134cdots$ 每一艘太空船从一个太空站驶往任一太空站耗时均为 $1$。人们只能在太空船停靠太空站（或月球、地球）时上、下船。初始时所有人全在地球上，太空船全在初始站。试设计一个算法，找出让所有人尽快地全部转移到月球上的运输方案。

分析：建立分层图。从 $S$ 向每一天的地球连一条容量为 $inf$ 的边；从每一天的月球向 $T$ 连一条容量为 $inf$ 的边；从每一天的节点向下一天的对应节点连一条容量为 $inf$ 的边；对于每一艘飞船，从每一天的位置向下一天的位置连一条容量为 $H_i$ 的边。枚举天数建图，跑最大流直到不小于总人数即可。

14.孤岛营救问题

链接：「网络流 24 题」孤岛营救问题

题意：迷宫的外形是一个长方形，其南北方向被划分为 $n$ 行，东西方向被划分为 $m$ 列，于是整个迷宫被划分为 $n times m$ 个单元。南北或东西方向相邻的 $2$ 个单元之间可能互通，也可能有一扇锁着的门，或者是一堵不可逾越的墙。迷宫中有一些单元存放着钥匙，并且所有的门被分成 $p$ 类，打开同一类的门的钥匙相同，不同类门的钥匙不同。大兵瑞恩被关押在 $(n,m)$ 单元里，并已经昏迷。迷宫只有一个入口，在 $(1,1)$ 单元。麦克从一个单元移动到另一个相邻单元的时间为 $1$，拿取所在单元的钥匙的时间以及用钥匙开门的时间可忽略不计。试设计一个算法，帮助麦克以最快的方式到达瑞恩所在单元，营救大兵瑞恩。

分析：将获得钥匙的状态压成二进制，对每一个状态建一层图，跑分层图最短路。

15.汽车加油驾驶问题

链接：「网络流 24 题」汽车加油行驶问题

题意：给定一个 $Ntimes N$ 的方形网格，设其左上角为起点，坐标为 $(1,1)$ ，$X$ 轴向右为正， $Y$ 轴向下为正，每个方格边长为 $1$ 。一辆汽车从起点出发驶向右下角终点 $(N,N)$ 。在若干个网格交叉点处，设置了油库。汽车在行驶过程中应遵守如下规则：汽车只能沿网格边行驶，装满油后能行驶 $K$ 条网格边；出发时汽车已装满油，在起点与终点处不设油库；汽车经过一条网格边时，若其 $X$ 坐标或 $Y$ 坐标减小，则应付费用 $B$ ，否则免付费用；汽车在行驶过程中遇油库则应加满油并付加油费用 $A$；在需要时可在网格点处增设油库，并付增设油库费用 $C$ (不含加油费用 $A$ )。求出汽车从起点出发到达终点的一条所付费用最少的行驶路线。

分析：令 $f(i,j,k)$ 为点 $(i,j)$ 剩余油量为 $k$ 的最小费用，跑最短路。

16.数字梯形问题

链接：「网络流 24 题」数字梯形

题意：给定一个由 $n$ 行数字组成的数字梯形。梯形的第一行有 $m$ 个数字。从梯形的顶部的 $m$ 个数字开始，在每个数字处可以沿左下或右下方向移动，形成一条从梯形的顶至底的路径。分别遵守以下规则：从梯形的顶至底的 $m$ 条路径互不相交；从梯形的顶至底的 $m$ 条路径仅在数字结点处相交；从梯形的顶至底的 $m$ 条路径允许在数字结点相交或边相交。将按照三个规则计算出的最大数字总和输出。

分析：从 $S$ 向顶部的每一个点连一条容量为 $1$ 费用为 $0$ 的边。规则一：拆点之后跑费用流；规则二：不拆点，跑费用流；规则三：把边的容量改为 $inf$ 。

17.运输问题

链接：「网络流 24 题」运输问题

题意：公司有 $m$ 个仓库和 $n$ 个零售商店。第 $i$ 个仓库有 $a_i$ 个单位的货物；第 $j$ 个零售商店需要 $b_j$ 个单位的货物。货物供需平衡，即 $sumlimits_{i = 1} ^ m a_i = sumlimits_{j = 1} ^ n b_j$ 。从第 $i$ 个仓库运送每单位货物到第 $j$ 个零售商店的费用为 $c_{ij}$ 。试设计一个将仓库中所有货物运送到零售商店的运输方案，使总运输费用最少。

分析：从 $S$ 向仓库连一条容量为 $a_i$ 费用为 $0$ 的边；从商店向 $T$ 连一条容量为 $b_j$ 费用为 $0$ 的边；从仓库向商店连一条容量为 $inf$ 费用为 $c_{ij}$ 的边，跑费用流即可。

18.分配工作问题

链接：「网络流 24 题」分配问题

题意：有 $n$ 件工作要分配给 $n$ 个人做。第 $i$ 个人做第 $j$ 件工作产生的效益为 $c_{ij}$ 。试设计一个将 $n$ 件工作分配给 $n$ 个人做的分配方案，使产生的总效益最大。

分析：二分图最大权匹配，常规建图跑费用流即可。

19.负载平衡问题

链接：「网络流 24 题」负载平衡

题意：公司有 $n$ 个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最少搬运量可以使 $n$ 个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。

分析：由于总量是固定的，我们可以得出每个仓库的最终储货量，令 $a_i$ 表示原有储货量-最终储货量。对于每一个仓库，拆成两个点 $x_i$ 和 $y_i$ ，一个代表供应，一个代表需求。若 $a_i>0$ ，从 $S$ 向 $x_i$ 连一条容量为 $a_i$ 费用为 $0$ 的边；若 $a_i<0$ ，从 $y_i$ 向 $T$ 连一条容量为 $-a_i$ 费用为 $0$ 的边；对于两个相邻的顶点 $j$ ，从 $x_i$ 分别向 $x_j$ 和 $y_j$ 连一条容量为 $inf$ 费用为 $1$ 的边。跑最小费用最大流即可。

20.深海机器人问题

链接：「网络流 24 题」深海机器人问题

题意：潜艇内有多个深海机器人。潜艇到达深海海底后，深海机器人将离开潜艇向预定目标移动。深海机器人在移动中还必须沿途采集海底生物标本，沿途生物标本由最先遇到它的深海机器人完成采集。每条预定路径上的生物标本的价值是已知的，而且生物标本只能被采集一次。本题限定深海机器人只能从其出发位置沿着向北或向东的方向移动，而且多个深海机器人可以在同一时间占据同一位置。用一个 $P times Q$ 网格表示深海机器人的可移动位置。西南角的坐标为 $(0,0)$ ，东北角的坐标为 $(Q,P)$ 。给定每个深海机器人的出发位置和目标位置，以及每条网格边上生物标本的价值。计算深海机器人的最优移动方案，使深海机器人到达目的地后，采集到的生物标本的总价值最高。

分析：每条边的贡献只能计算一次，考虑拆边：一条边容量为 $1$ 费用为价值，一条边容量为 $inf$ 费用为 $0$ 。跑最小费用最大流即可。

21.最长 k 可重区间集问题

链接：「网络流 24 题」最长 k 可重区间集

题意：给定实直线 $L$ 上 $n$ 个开区间组成的集合 $I$，和一个正整数 $k$，试设计一个算法，从开区间集合 $I$ 中选取出开区间集合 $S subseteq I$ ，使得在实直线 $L$ 的任何一点 $x$，$S$ 中包含点 $x$ 的开区间个数不超过 $k$ 。且 $sumlimits_{z in S} | z |$ 达到最大。这样的集合 $S$ 称为开区间集合 $I$ 的最长 $k$ 可重区间集。 $sumlimits_{z in S} | z |$ 称为最长 $k$ 可重区间集的长度。对于给定的开区间集合 $I$ 和正整数 $k$，计算开区间集合 $I$ 的最长 $k$ 可重区间集的长度。

分析：离散化区间的所有端点，从小到大为 $x_1,x_2,cdots x_m$ 。从 $S$ 向 $1$ 连一条容量为 $k$ 费用为 $0$ 的边；从 $m$ 向 $T$ 连一条容量为 $k$ 费用为 $0$ 的边；从 $i$ 向 $i+1$ 连一条容量为 $k$ 费用为 $0$ 的边；对于每一个区间，从其左端点的对应顶点向右端点的对应顶点连一条容量为 $1$ 费用为区间长度的边。跑最小费用最大流即可。

22.最大 k 可重线段集问题

链接：「网络流 24 题」最长k可重线段集问题

题意：给定平面 $xoy$ 上 $n$ 个开线段组成的集合 $I$，和一个正整数 $k$ 。从开线段集合 $I$ 中选取出开线段集合 $Sin I$ , 使得在 $x$ 轴上的任何一点 $p$ ，$S$ 中与直线 $x=p$ 相交的开线段个数不超过 $k$ ，且 $sum_{text{z} in text{S}}|z|$ 达到最大。这样的集合 $S$ 称为开线段集合 $I$ 的最长 $k$ 可重线段集的长度。对于任何开线段 $z$ ，设其端点坐标为 $( x_0 , y_0 )$ 和 $( x_1 , y_1 )$ ，则开线段 $z$ 的长度 $|text{z}|$ 定义为： $|z| = lfloor sqrt{ ( x_1 - x_0 ) ^ 2 + ( y_1 - y_0 )^2 } rfloor$。对于给定的开线段集合 $I$ 和正整数 $k$ ，计算开线段集合 $I$ 的最长 $k$ 可重线段集的长度。

分析：和上一道题基本一致，为了避免线段与 $x$ 轴垂直的情况，需要将所有的端点坐标 $times 2$ ，然后左端点 $-1$ 。

23.火星探险问题

链接：「网络流 24 题」火星探险问题

题意：登陆舱着陆后，探测车将离开登陆舱向先期到达的传送器方向移动。探测车在移动中还必须采集岩石标本，每一块岩石标本由最先遇到它的探测车完成采集。每块岩石标本只能被采集一次。岩石标本被采集后，其他探测车可以从原来岩石标本所在处通过。探测车不能通过有障碍的地面。本题限定探测车只能从登陆处沿着向南或向东的方向朝传送器移动，而且多个探测车可以在同一时间占据同一位置。如果某个探测车在到达传送器以前不能继续前进，则该车所采集的岩石标本将全部损失。用一个 $Ptimes Q$ 网格表示登陆舱与传送器之间的位置。登陆舱的位置在 $(X_1,Y_1)$ 处，传送器的位置在 $(X_P,Y_Q)$ 处。给定每个位置的状态，计算探测车的最优移动方案，使到达传送器的探测车的数量最多，而且探测车采集到的岩石标本的数量最多。

分析：将原图中的每一个顶点拆成两个点：若其为岩石顶点，从 $i$ 向 $i'$ 连一条容量为 $1$ 费用为 $1$ 的边；若其为非障碍点，从 $i$ 向 $i'$ 连一条容量为 $inf$ 费用为 $0$ 的边；对于相邻的点 $j$ ，从 $i'$ 向 $j$ 连一条容量为 $inf$ 费用为 $0$ 的边。从 $S$ 向 $(X_1,Y_1)$ 连一条容量为探测车数量费用为 $0$ 的边；从 $(X_P,Y_Q)$ 向 $T$ 连一条容量为探测车数量费用为 $0$ 的边。跑最小费用最大流即可。