线性规划与网络流24题

LojLoj上去掉了一题:机器人路径规划问题,所以就不做啦。

网络流24(23)题题面

[TOC]

题解

搭配飞行员

​ 题解:网络最大流

​ 二分图最大匹配,可以用容易实现的HungaryHungary算法O(n3/n(m+n)O(n^3/n(m+n),也可以用网络流建图,用DinicDinic跑二分图的复杂度是O(nm)O(\sqrt n*m)别问我为什么。

​ 新建源点S,汇点T,从S向每个正驾驶连一条容量为1的边,每个副驾驶向T连一条容量为1的边,对于每个可以匹配的正驾驶和副驾驶,从正驾驶向副驾驶连一条容量为1的边,跑出来的最大流就是答案。

太空飞行计划

​ 题解:网络最小割

​ 不妨假设全部收益都得到,而不花费费用。新建源点S,汇点T。

​ 从S向每个实验连一条容量为收益的边,每个实验向器械连一条容量为infinf的边,每个器械向 T连一条容量为购买费用的边。

​ 此时求最小割,如果在S集,说明这个实验做,如果在T集,说明这个实验不做。

​ 显然,容量为infinf的边不能被割去,所以如果在S集,必须满足右边全部的实验器材都买了。那么S-最小割就是答案。(最小割=最大流,证明见算导或相关论文)

最小路径覆盖

​ 题解:网络最大流

​ 新建源点S,汇点T。

​ 我们把每个点拆成两个点i1i_1i2i_2,对于边i>ji->j,连一条i1>j2i_1->j_2,容量为1的边,对于每个点,连SSi1i_1容量为1的边,连i2i_2到T容量为1的边。

​ 此时求最大流,如果流过一条i1i_1j2j_2的边,说明可以把以ii结尾的点和以jj开头的两条路径合并起来,变成一条路径。而答案要最小路径覆盖,也就是总点数-合并的次数(最大流)。

​ 因为是DAG,所以不会出现环。

魔术球问题

​ 题解:网络最大流

​ 如果我们已知答案AnsAns,要判断放1~Ans最少要几根柱子,我们可以这么做:

​ 对于每个数字ii,如果存在jj,满足j>ij>i,并且i+ji+j是完全平方数,那么从iijj连一条边,连完之后显然这是一个DAG,求出最小路径覆盖就是需要的柱子(做法同最小路径覆盖)

​ 那么这时候我们可以二分答案然后判定,但是基于残量网络的优秀性质,我们可以直接枚举答案,对于一个新节点,重新加入相关边,并在残量网络上跑最大流。到枚举到第一个不可行的AnsAns,答案就是Ans1Ans-1

​ 输出方案的时候删掉最后两个点,重新跑最大流(或者删除相关容量)。

圆桌聚餐

​ 题解:网络最大流

​ 新建源点S,汇点T。

​ 从S到每个单位容量为rir_i的边,从圆桌向T连一条容量为CiC_i的边,每个单位向每个圆桌连一条容量为ii的边。

​ 跑最大流后看哪些边被流过即可。

最长递增子序列

​ 题解:网络最大流

​ 注意题目是非严格递增QAQ。

​ 第一问是经典的DP(可以用O(n2)O(n^2)做法水),此时得到dpdp数组f[i]f[i]表示ii结尾的最长

​ 第二问可以把每个点拆点,限制流量不超过1(从入点到出点容量为1的边),从S向f[i]f[i]为1的入点容量为1的边,从f[i]f[i]ansans的出点边向T连一条容量为1的边。

​ 对于可以转移的,并且f[i]+1=f[j](i<j,a[i]<=a[j])f[i]+1=f[j](i<j,a[i]<=a[j]),从i的出点向j的入点一条容量为1的边,然后跑网络最大流即可。

​ 对于第三问,只需要把1和n的容量限制加上infinf即可。此时再跑网络最大流即可。

试题库

​ 题解:网路最大流

​ 新建源点S,汇点T。

​ 试题向类型建容量为1 的边,源点S向试题连容量为1的边,类型向汇点T连容量为需要题数的边,跑网络最大流看是否满流。

​ 输出方案看哪些试题向类型的边被流过。

方格取数

​ 题解:网络最小割

​ 首先对网格进行黑白染色。

​ 然后假设得到了所有答案。

​ 新建源点S,汇点T,从S向所有白色格子连一条容量为其值的边,所有黑色格子向T连一条容量为其值的边,所有白色格子向其相邻的黑色格子连一条容量为infinf的边,容易发现此时求最小割即最少减少的答案——如果要选一个白色格子,必须保证其相邻的黑色格子不选(割掉),选黑色格子同理。

餐巾计划

​ 题解:有上下界的最小费用流

​ 把每天拆点,定义为入点和出点。

​ 从入点到出点连一条上下界容量都为当天需要毛巾,费用为0的边,表示这天使用了这么多毛巾。

​ 从S向所有入点连一条容量为infinf,费用为购买新毛巾的价格,表示每天都可以新购入毛巾。——此处建图也可以全部第一天买。

​ 从每天的入点向下一天(如果有)的入点连一条容量为infinf,费用为0的边,表示前一天没用过的下一天还能用。

​ 从每天的出点向慢洗后那天的入点连一条容量为infinf,费用为慢洗的价格的边。

​ 从每天的出点向快洗后那天的入点连一条容量为infinf,费用为快洗的价格的边。

​ 从每一天的出点向T连一条边,表示用过了扔了。

​ 此时跑上下界最小费用最大流即可。(显然有解)

软件补丁

​ 题解:状态压缩,最短路

​ 把拥有bug压缩成一个二进制状态,依次判断m条可否转移(可以不显示建图)。类似于最短路做法,时间复杂度O(2nm)O(2^nm)

数字梯形

​ 题解:最大费用最大流

​ PS:这是一个等腰梯形

​ 对于第一问。

​ 对每个点拆点,中间连一条容量为1,费用为其值的边(实现可以用其值的相反数)

​ 从源点S向第一层的每一个点连一条容量为1,费用为0的边。

​ 对于每个点的出点,向它左下角和右下角的点的入点连一条容量为1,费用为0的边。

​ 从最后一层的出点向T点连一条容量为infinf,费用为0的边。

​ 此时求最大费用最大流,即为所要结果

​ 对于第二问,在第一问基础上只需要将每个点拆开的中间容量为infinf即可。

​ 对于第三问,在第二问基础上只需要将到左下角,右下角的边的容量改成(增加)infinf即可。

运输问题

​ 题解:最小费用最大流,最大费用最大流

​ 新建源点S,汇点T。

​ 从源点S到所有仓库一条容量为aia_i费用为0的边,从所有商店到汇点容量为bjb_j费用为0的边。从每个仓库到每个商店连一条容量为infinf,费用为c[i]c[i]的边,跑最小费用最大流和最大费用最大流(只需要把边取反,再答案取反即可)

分配问题

​ 题解:最小费用最大流,最大费用最大流

​ 新建源点S,汇点T。

​ 从源点S到所有仓库一条容量为1费用为0的边,从所有商店到汇点容量为1费用为0的边。从第ii个仓库到第jj个商店连一条容量为1,费用为c[i][j]c[i][j]的边,跑最小费用最大流和最大费用最大流(只需要把边取反,再答案取反即可)

负载平衡

​ 题解:最小费用最大流

​ 将每个数都减去平均数,得到A数组。

​ 对于A[i]>0A[i]>0的,从S向ii连一条容量为A[i]A[i]的边,否则从ii向T连一条容量为A[i]-A[i]的边

​ 每个点向相邻的两个点(注意是环)连容量为infinf,费用为1的边。

​ 跑最小费用最大流即是答案。

最长 k 可重区间集

​ 题解:最大费用最大流

​ 首先离散化。

​ 定义w[i]=r[i]l[i]w[i] = r[i]-l[i]表示选择这条线段的收益。

​ 对于每个点,从iii+1i+1连一条容量为infinf,费用为0的边。

​ 从S向第一个点连一条容量为KK,费用为0的边。

​ 从最后一个点向T连一条容量为KK,费用为0的边。

​ 对于每条线段,从l[i]l[i]r[i]r[i]连一条容量为1,费用为w[i]w[i]的边。

​ 此时跑S到T的最大费用最大流就是答案。

​ 每条增广路是单向的,会经过若干线段到达T,每个点最多只经过K次。

最长k可重线段集问题

​ 题解:最大费用最大流

​ 做法同上,定义w[i]=dist(Segment)w[i] = dist(Segment),注意是开线段。

​ 由于可能有和y轴平行的线段,作一下处理:

​ 对于每个l[i]l[i],r[i]r[i]都乘上2。

​ 如果l[i]=r[i]l[i]=r[i],那么l[i]1l[i]-1,否则l[i]+1l[i]+1

​ 注意到这样的话不会对其它线段造成影响,而且这个点也最多K次。

星际转移

​ 题解:网络最大流

​ 枚举答案,对于小于等于答案的每个时刻,建立那个时候的地球,各空间站,月球这些点。

​ 从S向0时刻的地球连一条容量为k的边。

​ 从上一个时刻的点向这个时刻连一条容量为infinf的边,表示可以滞留。

​ 从上一个时刻太空船所在位置的点向这个时刻太空船所在位置的点连一条容量为H[i]H[i]的边表示可以转移。

​ 从每个时刻的月球向T连一条容量为infinf的边,表示登月就结束。

​ 如果满流,说明答案可行,输出。

​ 如果(k+2)*(n+2)次后还不行说明不可行(或者用并查集单独判断是否联通)

孤岛营救问题

​ 题解:状态压缩,最短路

​ 注意钥匙🔑数量<=10<=10所以用一个二进制表示有哪些钥匙,然后跑分层图BFS得到最短路即可。

航空路线问题

​ 题解:最大费用最大流

​ 把每个城市拆点,1号节点和n号节点之间入点和出点连容量为2,费用为1的边,其它节点连容量为1费用为1的边。对于可以到达的,从出点到入点连容量为1(如果是1号点到n号点,连容量为2),费用为0的边。

​ 从1号点的入点到n号点的出点跑最大费用最大流,其实就是跑出两条路径。

​ 输出方案可以顺着哪些被流过的边,正着倒着做一下。

汽车加油行驶问题

​ 题解:最短路

​ 注意到k<=10k<=10,我们定义一个节点(i,j,k)(i,j,k)表示在位置(i,j)(i,j),其剩余油量为kk,那么从一个点向周围的点,(x,y,k1)(x,y,k-1)连边。

​ 如果到达的哪个点是加油站,那么应该是(i,j,满油)连边。

​ 此时求(1,1,满油)到(n,n,0~满油)的最短路即可。

深海机器人问题

​ 题解:最大费用最大流

​ 新建源点S,汇点T,每个点向右边,下面的点连2条边,第一条容量为1,费用为价值,第二条容量为infinf,费用为0,S到可以进入点容量为1,费用为0,可出去到T一条容量为1,费用为0的边,跑S到T的最大费用最大流即可。

火星探险问题

​ 题解:最大费用最大流

​ 每个点拆点,中间的边同上题,相邻的出点到入点,S到(1,1,入)一条容量为car,费用为0的边,最后一个点的出点到T容量为car,费用为0的边,求最大费用最大流。输出方案的时候只需要DFS一下,做完一条把流量返还即可。

骑士共存问题

​ 题解:网络最小割

​ 首先黑白染色,然后类似与方格染色建图,也就是先假设全部都选,然后减去最小割就是答案。

模板

头文件

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
//Hello Wolrd
//There is Special Pig Jiong in the world.
#include<cstdio>
#include<ctype.h>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
const int inf = 0x3f3f3f3f,oo = inf;
#define pc putchar
#define RG register
char __wzp[1<<15|1],*__S=__wzp+32768;
#define gc() (__S>=__wzp+32768?(__wzp[fread(__wzp,sizeof(char),1<<15,stdin)]=EOF),*((__S=__wzp)++):*(__S++))
inline ll read(){
RG ll x=0,f=1;RG char c=gc();
for(;!isdigit(c);c=gc())if(c=='-')f=-1;
for(;isdigit(c);c=gc())x=(x<<1)+(x<<3)+(c^48);
return x*f;
}
void write(ll x){
if(x<0)x=-x,pc('-');
if(x>=10)write(x/10);
putchar(x%10+'0');
}
#define rd read
#define mem(x,v) memset(x,v,sizeof(x))
#define pb push_back
#define mp make_pair
#define sqr(x) ((x)*(x))
#define lowbit(x) ((x)&(-(x)))
#define rep(i,a,b) for(RG int i=(a);i<(b);++i)
#define fin(x) {freopen(#x".in","r",stdin);}
#define y1 ________y1
const int N = ;
const int M = ;
int main(){
#define LOCAL
#ifdef LOCAL
fin(1);
#endif
return 0;
}

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
//配合T模板使用
#define N ????
#define M ????
struct Edge{
int to,nxt,cap;
Edge(){}
Edge(int to,int nxt,int cap):to(to),nxt(nxt),cap(cap){};
}edge[M*2];
int first[N],cur[N],nume;
void Addedge(int a,int b,int c){
edge[nume] = Edge(b,first[a],c);first[a] = nume++;
edge[nume] = Edge(a,first[b],0);first[b] = nume++;
}
int q[N],dis[N],S,T;
bool bfs(){
int u,v,front,rear;mem(dis,-1);
for(front=rear=0,dis[u=q[rear++]=T]=1;front<rear;)
for (int u=q[front++],e=first[u];~e;e=edge[e].nxt)
if(edge[e^1].cap && !~dis[v=edge[e].to])dis[q[rear++]=v]=dis[u]+1;
return dis[S]!=-1;
}
int dfs(int u,int flow){
if(u==T)return flow;
int used = 0,d,v;
for (int &e=cur[u];~e;e=edge[e].nxt){
if(edge[e].cap && dis[v=edge[e].to]==dis[u]-1 && (d = dfs(v,min(flow-used,edge[e].cap))))
edge[e].cap -= d,edge[e^1].cap += d,used += d;
if(used == flow) break;
}
if(!used)dis[u]=-1;
return used;
}
int dinic(){
int ans = 0;
for(;bfs();ans+=dfs(S,inf))
rep(i,0,N) cur[i] = first[i];
return ans;
}
int main(){
mem(first,-1);nume = 0;
S = ???,T = ???;
}

SPFA费用流模板

PS:最小费用最大流

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
//配合T模板使用
#define N 1005
#define M 20005
int S,T;
struct Edge{
int to,nxt,cap,cost;
Edge(){}
Edge(int to,int nxt,int cap,int cost):to(to),nxt(nxt),cap(cap),cost(cost){}
}edge[2*M];
int first[N],nume,n,m;
void Addedge(int a,int b,int cap,int cost){
edge[nume] = Edge(b,first[a],cap,cost);first[a] = nume++;
edge[nume] = Edge(a,first[b],0,-cost);first[b] = nume++;
}
int dis[N],vis[N],pre[N];
bool spfa(){
queue<int> q;
mem(dis,0x3f);
mem(vis,false);
mem(pre,-1);
dis[S]=0;
vis[S]=true;
q.push(S);
while(!q.empty()){
int u = q.front();q.pop();
vis[u] = false;
for (int e=first[u];~e;e=edge[e].nxt){
int v = edge[e].to;
if(edge[e].cap&&dis[v]>dis[u]+edge[e].cost){
dis[v]=dis[u]+edge[e].cost;
pre[v] = e;
if(!vis[v]){
q.push(v);
vis[v]=true;
}
}
}
}
return dis[T]!=inf;
}
int mcmf(){
int minflow,maxflow=0,mincost=0;
while(spfa()){
minflow = inf;
for(int i=pre[T];~i;i=pre[edge[i^1].to])
minflow = min(minflow,edge[i].cap);
for(int i=pre[T];~i;i=pre[edge[i^1].to])
edge[i].cap -= minflow,
edge[i^1].cap += minflow;
mincost += minflow * dis[T];
maxflow += minflow;
}
return mincost;
}
int main(){
mem(first,-1);nume = 0;
S = ??,T = ??;
}

部分代码的部分

出于懒惰给大家独立思考的目的,上面很多不详细,这里贴部分代码。

但是又出于懒惰美观,只帖部分代码的部分。

缺少部分一般为变量定义(自己写吧)和最大流(最小割),或者最小(大)费用最大流,这个往上面看吧。

骑士共存问题

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
#define encode(a,b) ((a) * (n) + (b) + (1))
int n,m,ans,A[205][205];
const int dx[8]={1,1,-1,-1,2,2,-2,-2};
const int dy[8]={2,-2,2,-2,1,-1,1,-1};
int main(){
mem(first,-1);nume = 0;
S = 0,T = n*n+1;
n = read(),m = rd();
ans = n*n-m;
mem(A,false);
rep(i,0,m){
int x = rd(),y = rd();
A[x-1][y-1] = true;
}
rep(i,0,n)rep(j,0,n){
if(A[i][j]) continue;
if((i+j)&1){
Addedge(S,encode(i,j),1);
rep(d,0,8){
int x = i + dx[d],y = j + dy[d];
if(x<0||y<0||x>=n||y>=n||A[x][y]) continue;
Addedge(encode(i,j),encode(x,y),inf);
}
}
else
Addedge(encode(i,j),T,1);
}
printf("%d\n",ans-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
48
49
int P,Q,turn[233];
#define encode(a,b) ((a) * (Q) + (b) + 1)
void dfs(int x,int y){
if(x==P-1&&y==Q-1) return;
int a=encode(x,y)*2,b=encode(x+1,y)*2-1,c=encode(x,y+1)*2-1;
if(x==P-1)b=-1;if(y==Q-1)c=-1;
for(int e=first[a];~e;e=edge[e].nxt){
if(e&1)continue;
int v = edge[e].to;
if(vis[e] >= edge[e^1].cap) continue;
if(v==b){
++vis[e];
turn[++*turn] = 0;
dfs(x+1,y);
return ;
}
if(v==c){
++vis[e];
turn[++*turn] = 1;
dfs(x,y+1);
return ;
}
}
}
int main(){
int car = read();
Q = read(),P = read();
S = 0,T = P*Q*2+1;
mem(first,-1);nume = 0;
Addedge(S,1,car,0);
Addedge(encode(P-1,Q-1)*2,T,car,0);
rep(i,0,P)rep(j,0,Q){
int x = read();
if(x==0) Addedge(encode(i,j)*2-1,encode(i,j)*2,inf,0); else
if(x==2) Addedge(encode(i,j)*2-1,encode(i,j)*2,inf,0),
Addedge(encode(i,j)*2-1,encode(i,j)*2,1,-1);
if(i!=P-1)Addedge(encode(i,j)*2,encode(i+1,j)*2-1,inf,0);
if(j!=Q-1)Addedge(encode(i,j)*2,encode(i,j+1)*2-1,inf,0);
}
mcmf();
mem(vis,0);
for(int i=1;i<=car;i++){
turn[0]=0;
dfs(0,0);
for(int j=1;j<=turn[0];j++)
printf("%d %d\n",i,turn[j]);
}
return 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
int pos[233][233];
int main(){
int tot=0;
int A=rd(),B=rd(),p=rd(),q=rd();
mem(first,-1);nume = 0;
rep(i,0,p+1)rep(j,0,q+1)pos[i][j]=++tot;
S=tot+1,T=S+1;
rep(i,0,p+1)rep(j,0,q){
int x = read();
Addedge(pos[i][j],pos[i][j+1],1,-x);
Addedge(pos[i][j],pos[i][j+1],inf,0);
}
rep(j,0,q+1)rep(i,0,p){
int x=read();
Addedge(pos[i][j],pos[i+1][j],1,-x) ;
Addedge(pos[i][j],pos[i+1][j],inf,0);
}
while(A--){
int k = rd(),x=rd(),y=rd();
Addedge(S,pos[x][y],k,0);
}
while(B--){
int k = rd(),x=rd(),y=rd();
Addedge(pos[x][y],T,k,0);
}
printf("%d\n",-mcmf());
return 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
int main(){
m = read(),n = read();
int tot = 0;
mem(first,-1);nume = 0;
S = tot++,T = tot++;
for(int i=1;i<=n;i++){
for(int j=1;j<=m+i-1;j++){
id[i][j][0] = tot++;
id[i][j][1] = tot++;
Addedge(id[i][j][0],id[i][j][1],1,-read());
}
}
for(int i=1;i<=n-1;i++){
for(int j=1;j<=m+i-1;j++){
Addedge(id[i][j][1],id[i+1][j][0],1,0);
Addedge(id[i][j][1],id[i+1][j+1][0],1,0);
}
}
for(int i=1;i<=m;i++)
Addedge(S,id[1][i][0],1,0);
for(int i=1;i<=n+m-1;i++){
Addedge(id[n][i][1],T,inf,0);
}
printf("%d\n",-mcmf());
for(int i=0;i<nume;i+=2) edge[i].cap+=edge[i^1].cap,edge[i^1].cap=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m+i-1;j++){
int e = pos[id[i][j][0]][id[i][j][1]];
edge[e].cap = inf;
}
}
printf("%d\n",-mcmf());
for(int i=0;i<nume;i+=2) edge[i].cap+=edge[i^1].cap,edge[i^1].cap=0;
for(int i=1;i<=n-1;i++){
for(int j=1;j<=m+i-1;j++){
edge[pos[id[i][j][1]][id[i+1][j][0]]].cap = inf;
edge[pos[id[i][j][1]][id[i+1][j+1][0]]].cap = inf;
}
}
printf("%d\n",-mcmf());
}

最长K可重区间集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int l[N],y[N*2],r[N],w[N],K;
int main(){
n = read(),K = read();
mem(first,-1);nume = 0;
for(int i=1;i<=n;i++){
l[i] = read(),r[i] = read();
if(l[i]>=r[i])swap(l[i],r[i]);
w[i] = r[i]-l[i];
y[++*y] = l[i],y[++*y] = r[i];
}
sort(y+1,y+1+*y);
*y = unique(y+1,y+1+*y) - y - 1;
for(int i=1;i<=n;i++){
l[i] = lower_bound(y+1,y+1+*y,l[i]) - y;
r[i] = lower_bound(y+1,y+1+*y,r[i]) - y;
}
S = 0,T = 2**y + 1;
Addedge(S,1,K,0);
Addedge(2**y,T,K,0);
for(int i=1;i<2**y;i++) Addedge(i,i+1,inf,0);
for(int i=1;i<=n;i++) Addedge(l[i],r[i],1,-w[i]);
printf("%d\n",-mcmf());
return 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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
map<string,int> id;
string name[205];
int main(){
n = read();m = read();
mem(first,-1);nume = 0;
for(int i=1;i<=n;i++){
string str;
cin >> str;
id[str] = i;
name[i] = str;
}
S = 1;T = n*2;
Addedge(1,1+n,2,-1);
for(int i=2;i<=n-1;i++){
Addedge(i,i+n,1,-1);
}
Addedge(n,n+n,2,-1);
while(m--){
string str;
cin >> str;
int x = id[str];
cin >> str;
int y = id[str];
if(x>y) swap(x,y);
if(x==1&&y==n)Addedge(x+n,y,2,0);
else Addedge(x+n,y,1,0);
}
int ans = mcmf(2);
if(ans == -1){
puts("No Solution!");
return 0;
}
printf("%d\n",ans-2);
cout << name[1] << endl;
mem(vis,false);
for(int e=first[n+1],j,k;~e;e=edge[e].nxt){
if(!edge[e].cap&&!(e&1)){
k = edge[e].to;
while(k){
cout << name[k] << endl;
vis[k] = true;
for(j=first[k+n],k=0;~j;j=edge[j].nxt){
if(!edge[j].cap&&!(j&1)){
k = edge[j].to;
break;
}
}
}
break;
}
}
for(int e=first[n],j,k;~e;e=edge[e].nxt){
if(!edge[e^1].cap&&(e&1)&&!vis[edge[e].to-n]){
k = edge[e].to-n;
while(k){
cout << name[k] << endl;
vis[k] = true;
for(j=first[k],k=0;~j;j=edge[j].nxt){
if(!edge[j^1].cap&&(j&1)){
k = edge[j].to - n;
break;
}
}
}
break;
}
}
return 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
int n,_P,_M,_F,_N,_S;
void solve(){
n = read(),_P = read(),_M = read(),_F = read(),_N = read(),_S = read();
S = 2*n+1,T=S+1,SS=T+1,TT=SS+1;
mem(first,-1);nume = 0;
for(int i=1;i<=n;i++){
Addedge(i+n,TT,inf,0);
int x = read();
Addedge(i,i+n,inf-x,0);
Addedge(i,T,x,0);
Addedge(S,i+n,x,0);
}
for(int i=1;i<=n;i++){
Addedge(SS,i,inf,_P);
if(i!=n) Addedge(i,i+1,inf,0);
if(i+_M<=n) Addedge(i+n,i+_M,inf,_F);
if(i+_N<=n) Addedge(i+n,i+_N,inf,_S);
}
Addedge(TT,SS,inf,0);
printf("%lld\n",mcmf());
}
int main(){
solve();
return 0;
}
文章目录
  1. 1. 题解
    1. 1.1. 搭配飞行员
    2. 1.2. 太空飞行计划
    3. 1.3. 最小路径覆盖
    4. 1.4. 魔术球问题
    5. 1.5. 圆桌聚餐
    6. 1.6. 最长递增子序列
    7. 1.7. 试题库
    8. 1.8. 方格取数
    9. 1.9. 餐巾计划
    10. 1.10. 软件补丁
    11. 1.11. 数字梯形
    12. 1.12. 运输问题
    13. 1.13. 分配问题
    14. 1.14. 负载平衡
    15. 1.15. 最长 k 可重区间集
    16. 1.16. 最长k可重线段集问题
    17. 1.17. 星际转移
    18. 1.18. 孤岛营救问题
    19. 1.19. 航空路线问题
    20. 1.20. 汽车加油行驶问题
    21. 1.21. 深海机器人问题
    22. 1.22. 火星探险问题
    23. 1.23. 骑士共存问题
  2. 2. 模板
    1. 2.1. 头文件
    2. 2.2. Dinic模板
    3. 2.3. SPFA费用流模板
  3. 3. 部分代码的部分
    1. 3.1. 骑士共存问题
    2. 3.2. 火星探险问题
    3. 3.3. 深海机器人问题
    4. 3.4. 数字梯形
    5. 3.5. 最长K可重区间集
    6. 3.6. 航空路线问题
    7. 3.7. 餐巾计划