网络流算法及例题

题单

来源：https://www.cnblogs.com/ticmis/p/13211073.html

编号	题目名字	题目模型	转化模型	完成情况
1	飞行员配对方案问题	二分图最大匹配	二分图	✅
2	孤岛营救问题	分层图最短路径	最短路径	✅
3	汽车加油行驶问题	分层图最短路径	最短路径	✅
4	软件补丁问题	最小转移代价	最短路径	✅
5	星际转移问题	分层图转移	最大流
6	太空飞行计划问题	最大权闭合图	最小割	✅
7	最小路径覆盖问题	有向无环图最小路径覆盖	最大流	✅
8	魔术球问题	有向无环图最小路径覆盖	最大流	✅
9	圆桌问题	二分图多重匹配	最大流	✅
10	试题库问题	二分图多重匹配	最大流	✅
11	分配问题	二分图最佳匹配	费用流	✅
12	方格取数问题	二分图点权最大独立集	最小割	✅
13	骑士共存问题	二分图点权最大独立集	最小割	✅
14	负载平衡问题	费用流水题模板题	费用流	✅
15	运输问题	费用流水题模板题	费用流	✅
16	最长递增子序列问题	限制性带权路径	最大流	✅
17	航空路线问题	限制性带权路径	费用流	✅
18	数字梯形问题	限制性带权路径	费用流	✅
19	最长k可重区间集问题	限制性带权路径	费用流	✅
20	最长k可重线段集问题	限制性带权路径	费用流	✅
21	深海机器人问题	限制性带权路径	费用流	✅
22	火星探险问题	限制性带权路径	费用流
23	餐巾计划问题	线性规划网络流优化	费用流

最短路模型

「网络流 24 题」孤岛营救 *

「网络流 24 题」软件补丁 *

均可直接「状压」跑最短路。

「网络流 24 题」汽车加油行驶问题 *

分层图最短路。

最大流模型

const int N=1e6+5,M=2e6+5;
int head[N],dis[N],cur[N],ver[M],edge[M],nxt[M],tot=1,S,T;
void init(){for (int i=0;i<=tot;i++) ver[i]=edge[i]=nxt[i]=0;tot=1;for (int i=1;i<=T;i++) head[i]=0;
}
void add(int u,int v,int w){ver[++tot]=v,edge[tot]=w;nxt[tot]=head[u],head[u]=tot;
}
void append(int u,int v,int w){add(u,v,w);add(v,u,0);
}
bool bfs(){for (int i=1;i<=T;i++) dis[i]=0,cur[i]=head[i];queue<int> q;q.push(S),dis[S]=1;while (!q.empty()){int u=q.front(); q.pop();for (int i=head[u];i;i=nxt[i]){int v=ver[i],w=edge[i];if (w&&!dis[v]){dis[v]=dis[u]+1;if (v==T) return 1;q.push(v);}}}return 0;
}
int dfs(int u,int flow){if (u==T) return flow;int sum=0;for (int i=cur[u];i;cur[u]=i=nxt[i]){int v=ver[i],w=edge[i];if (w&&dis[v]==dis[u]+1){int f=dfs(v,min(w,flow));edge[i]-=f,edge[i^1]+=f;sum+=f,flow-=f;if (!flow) break;}}if (!sum) dis[u]=0;return sum;
}
int Max_flow(){int res=0;while (bfs()) res+=dfs(S,1e9);return res;
}

类二分图

特点：用于处理 $n$ 场比赛 $m$ 个人、 $n$ 种类型 $m$ 个元素等含有 $2$ 种相关元素的题目。
技巧：可以建立二分图，并通过超级汇点、超级源点来进行网络流。
模型转化：DAG 最小路径覆盖

「网络流 24 题」搭配飞行员 *

二分图。

「网络流 24 题」试题库 *

建出 $n + k$ 个点的类二分图即可。

「网络流 24 题」圆桌聚餐 *

$m$ 个点代表不同单位， $n$ 个点代表餐桌，类二分图。

洛谷 P3425 [POI 2005] KOS-Dicing

「最大值最小」用二分。

建出 $n + m$ 个点，其中源点向每个比赛连 $1$ 的边，每个比赛分别向对应的 $2$ 人连 $1$ 的边，每个人向汇点连 $\text{Mid}$ 的边。

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

「网络流 24 题」魔术球 *

最小路径数 $=$ 总点数 $-$ 被覆盖边数

把每个点拆为入点和出点，若在原图存在 $u\to v$ ，则在新图上从 $u$ 的出点连向 $v$ 的入点，并将 $S$ 连向所有出点，所有入点连向 $T$ 。

最小割

特点：取了某些元素，则另一些元素就不能取，使得价值最值化；且可以将元素划分为 $2$ 个集合，使得在每个集合内取任意元素都合法。
技巧：建立二分图连接集合 $U$ 和 $V$ ，并在 $U\to V$ 连接 $+\infin$ 的边， $S\to U$ 设为 $U$ 中元素的权值， $V\to T$ 设为 $V$ 中元素的权值，即可跑最小割（最大流）。
模型转化：网格图相邻操作 / 最大权闭合子图（每个点有代价，选择其中一些点，若某个集合内所有点都被选择会有一个收益，求净利润最大值）

「网络流 24 题」方格取数

「网络流 24 题」骑士共存 *

将格子黑白染色，即可分为 $2$ 个集合。根据上述方式建图跑最大流即可。

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

洛谷 P4174 [NOI2006] 最大获利 *

实验与仪器分为两个集合，求出的最小割即为「不选择的实验的价值和 $+$ 选择的仪器的价格和」的最小值，总价值减去最小割即可。

ABC239G Builder Takahashi *

要注意输出方案的时候可能会有形成内部的环的流，不能输出。

洛谷 P4313 文理分科

洛谷 P1646 [国家集训队] happiness *

CF311E Biologist *

每个人建立一个点（想成二分图了，这样会导致可能会同时割掉一个人的文理）， $S$ 向它们连容量为理科的边权，它们向 $T$ 连文科的边权。

对于同文同理，新建点即可。

ABC193F Zebraness

这题是不同 $+ 1$ ，所以可以通过间隔反色变为相同 $+ 1$ 。

路径法

特点：各点有分层的特质。
技巧：通过拆点限制经过点的流量，并且在相邻层间连边。

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

第一问 DP。

第二、三问，可以建立 $u\to v$ 的边，当且仅当 $f_v=f_u+1$ ，跑网络流。

但要注意每个点的流量只能为 $1$ ，于是可以把每个点拆为入点和出点，入点向出点连一条容量为 $1$ 的边。

费用流模型

const int N=1000005,M=2000005;
int head[N],ver[M],edge[M],cost[M],nxt[M],tot=1,S,T,dis[N],flow[N],pre[N],Maxflow,Mincost;
bool vis[N];
void add(int u,int v,int w,int c){ver[++tot]=v,edge[tot]=w,cost[tot]=c;nxt[tot]=head[u],head[u]=tot;
}
void append(int u,int v,int w,int c){add(u,v,w,c);add(v,u,0,-c);
}
void init(){for (int i=2;i<=tot;i++) ver[i]=edge[i]=cost[i]=nxt[i]=0;for (int i=1;i<=T;i++) head[i]=dis[i]=flow[i]=pre[i]=vis[i]=0;Maxflow=Mincost=0,tot=1;
}
bool SPFA(){queue<int> q;for (int i=1;i<=T;i++) dis[i]=1e9,flow[i]=0;dis[S]=0,flow[S]=1e9,q.push(S),vis[S]=1;while (!q.empty()){int u=q.front(); q.pop();vis[u]=0;for (int i=head[u];i;i=nxt[i]){int v=ver[i],w=edge[i],c=cost[i];if (dis[v]>dis[u]+c&&w){dis[v]=dis[u]+c;flow[v]=min(flow[u],w);pre[v]=i;if (!vis[v]) vis[v]=1,q.push(v);}}}return dis[T]<1e9;
}
void MCMF(){Maxflow=Mincost=0;while (SPFA()){Maxflow+=flow[T];Mincost+=dis[T]*flow[T];for (int i=T;i!=S;i=ver[pre[i]^1]) edge[pre[i]]-=flow[T],edge[pre[i]^1]+=flow[T];}
}