【学习笔记】网络流常见模型(一)：有限制的图上最短（长）路
辰星凌
2019-08-30 17:42:49
# **【学习笔记】网络流常见模型(一)：有限制的图上最短（长）路**
[$\mathcal{My}$ $\mathcal{Blog}$](https://www.cnblogs.com/Xing-Ling/p/11436314.html)
------
*网络瘤，网络瘤，网络建模最毒瘤*
-----
## **【大前言】**
网络流的大部分题都在考**问题分析和转换**，以及对**状态维护**的考虑（$DP$ $?$ 嗯哼 $?$），综合起来就是考**问题建模**。
只要建立出了合适的模型，只需要背一遍模板就 $ok$ 了，有些题目甚至都不需要跑网络流，直接上最短路，$bfs$或者$dfs$（只要有耐心去思考，$dp$ 也能解决一部分题目），由于网络流算法过程的本质是贪心，所以在特定的情况下还可以直接**贪心** $+$ **模拟**。
作为史上第一届提高组 $CSPer$，先在这里大胆地立个 $flag$： ~~(NOIP)~~ $CSP$ 不考网络流！
关于网络流中更高深的东西还没有作深入研究，主要还是学一下基础建模思想。
网络流基础知识康这里：[【学习笔记】网络流算法简单入门](https://www.luogu.org/blog/ChenXingLing/post-xue-xi-bi-ji-wang-lao-liu-suan-fa-jian-dan-ru-men)
### **【进入正题】**
有时候我们可能会遇到这样一种题目：一眼看过去瞬间就想到最短（长）路，仔细想想后又被它鬼畜的限制条件给吓住，可能我们会想到状压，但状压并不是万能的，数据过大时就只能另想办法了。这时候可以将**费用流**作为一种待选思路。
其实这种**带限制的图上最短（长）路**应该是网络流建模中最简单的类型了，涉及到的方法都比较基础，所以下文在分类讨论时不考虑复杂的建模方法。
------
## **一：【建模思路】**
建模是最难的部分，但要相信，一些类型的题目也是有套路可寻的。
------
### **1.【确定建模方法】**
首先我们要明确这**鬼畜的限制条件**都有些什么。
例如：
**找出** $K$ **条**最短路。
找出两条**不相交**的最短路。
**每个点、边**最多只能经过 $K$ 次。
**特定的点、边**最多只能经过 $K$ 次。
$...$
常见的可以分为两类：
#### **(1). 【局部相同】**
**特征：** 一大类（或者几大类）的点、边都有着相同的限制条件。
**方法：** **分层图**。每一层就表示限制条件中的一种状态，这种状态有时比较明显，有时需要用状压将其简化。
如果有天数的概念，并且到达指定天数后就结束或者花费 $XXX$ 重置天数，诸如此类的问题可以按照天数进行分层，在图上的某个位置 $x$ 的某一层 $k$ 代表在 $x$ 这个位置，时间为第 $k$ 天的状态。
#### **(2). 【局部不同】**
**特征：** 每个点、边都会给出不同的限制条件（可能有少数相同，看给出的数据如何）。
**方法：** **拆点**。拆点是最玄学的方法，一道莫名其妙的题，可能一波神仙操作后就变成了最大流。
但在图上面要求似乎没那么高。最简单的是拆成**入点**和**出点**，如果题目给出了**点权**或者**点的最大允许经过次数**，就在拆出的**入点**和**出点**之间连一条**流量为经过次数**，**费用为点权**的边，这样就可以把点权变成边权，同时实现了点的经过次数限制（如果某些边有经过次数限制的话，也可以将其作为边流量）。
#### **(3). 【全局相同】**
**特征：** 整体限制。
**方法：** **超级源点和超级汇点**。这种方法非常好用，凡是看到网络流的题，都可以先建个**超源和超汇**，不仅对答案没有影响，还能帮助我们思考问题，利用它去完成很多不太好解决的限制条件。
**超源和超汇**可以轻松解决存在**多个起点和终点**的情况。
在求**非完备匹配二分图的可行边、必须边**时，**超汇**还有构造增广路的作用，这里不做讨论。
如果题目要求**找出** $K$ **条路径**使得经过的边权总和最小，那么可以让**超源**和起点连流量为 $K$ 的边，**超汇**同理，对于图里面的点则按具体要求连边。
为什么这样做就是对的呢？利用费用流的特性，即最大流为前提，在此基础上求最小（大）花费，因此路径数可以人为设定，只要有解，最后一定会跑出最大流（即人为设定的路径数）。
------
### **2.【思考建图时的状态转移】**
就像 $dp$ 一样，需要做到**不重不漏**（有时候“**重**”似乎并不会造成影响，但会降低算法效率）
所谓的“**状态转移**”就是计算从一个状态到另一个状态需要消耗的费用，流量等等。
这里的“**状态**”有**分层**后的**层数**，**拆点**后的**入点和出点**，还有单纯的从一个位置（坐标）到达另一个位置（坐标），这些都是需要考虑的东西。
------
### **3.【认真计算空间复杂度】**
最好是把空间抠死（抠到**最小空间** $+10$ 这种程度），因为开太小会 $RE$，开太大又可能 $TLE$。
$TLE$ 可能有人不相信，但我反正是栽了无数次跟头。
有时候算好了总边数，结果总点数算错。还有拆点时为了好写导致中间空了编号很多没有使用，于是在跑 $SPFA$ 前的初始化 $dis$ 时，巨大的点数狠狠地将一个个 $TLE$ 拍到了我的脸上。
一些可能需要注意的地方：
$(1).$ 如果分出 $[1,K]$ 层后还使用了第 $0$ 层，那么点数应该是 $n*(K+1)$ 。
$(2).$ 计算点个数时别忘了还有**超源**和**超汇**。
$(3).$ 算出的总边数还要乘以 $2$（因为要建反边供算法中的“反悔”操作）。
$(4).$ 与**超源**和**超汇**相连的边也要计算。
------
### **4.【跑图】**
建好了图就是愉快的套模板时刻啦，如果网络流中的所有边**流量**都为 $1$，可以发现和最短路算法写出来没什么区别（$EK$ 跑费用流毕竟是自带 $SPFA$ 的）。
------
## **二：【例题】**
前面说的都比较抽象，现在来看几道例题。
（$1,2,3$ 为散乱的图，$4,5,6$ 为方格图）
注：下文中说到连“**流量**”为 $XX$ “**费用**”为 $XX$ 的边，表达的意思是**残留流量**和**单位费用**。
------
### **1.【运输问题】**
传送门：[运输问题 $[P4015]$](https://www.luogu.org/problem/P4015) [$[Loj6011]$](https://loj.ac/problem/6011)
**（难度：简单）**
#### **【分析】**
只需要建个**超源和超汇**就解决啦$QAQ$。
$(1).$ **超源**与 $i \in [1,n]$ 连**流量为** $a[i]$ **费用为** $0$ 的边。
$(2).$ $j \in [1,m]$ 与**超汇**连**流量为** $b[j]$ **费用为** $0$ 的边。
（注意连边的方向，是**超源**指向起点，终点指向**超汇**，之后不再提醒）
$(3).$ 然后 $i \in [1,n]$ 与 $j \in [1,m]$ 连**流量为** $inf$ **费用为** $cost[i][j]$ 的边。
至于最大费用，清空数组后把 $cost$ 全变为负数再跑一遍即可。
#### **【Code】**
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=205,M=10205,inf=2e9;//点数: 100+100+2=202, 边数: 100*100+100*2=10200
int o=1,n,m,h,t,st,ed,cyf[N],pan[N],pre[N],dis[N],head[N],Flow[N][2],Cost[N][N];LL mincost,maxflow;
struct QAQ{int w,to,next,flow;}a[M<<1];queue<int>Q;
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline void add(Re x,Re y,Re z,Re w){a[++o].flow=z,a[o].w=w,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void add_(Re a,Re b,Re flow,Re w){add(a,b,flow,w),add(b,a,0,-w);}
inline int SPFA(Re st,Re ed){
for(Re i=0;i<=ed;++i)dis[i]=inf,pan[i]=0;
Q.push(st),pan[st]=1,dis[st]=0,cyf[st]=inf;
while(!Q.empty()){
Re x=Q.front();Q.pop();pan[x]=0;
for(Re i=head[x],to;i;i=a[i].next)
if(a[i].flow&&dis[to=a[i].to]>dis[x]+a[i].w){//最小费用
dis[to]=dis[x]+a[i].w,pre[to]=i;
cyf[to]=min(cyf[x],a[i].flow);
if(!pan[to])pan[to]=1,Q.push(to);
}
}
return dis[ed]!=inf;
}
inline void EK(Re st,Re ed){
while(SPFA(st,ed)){
Re x=ed;maxflow+=cyf[ed],mincost+=(LL)cyf[ed]*dis[ed];
while(x!=st){
Re i=pre[x];
a[i].flow-=cyf[ed];
a[i^1].flow+=cyf[ed];
x=a[i^1].to;
}
}
}
int main(){
in(n),in(m),st=n+m+1,ed=st+1;
for(Re i=1;i<=n;++i)in(Flow[i][0]),add_(st,i,Flow[i][0],0);//超源->仓库
for(Re i=1;i<=m;++i)in(Flow[i][1]),add_(n+i,ed,Flow[i][1],0);//商店->超汇
//防止代表仓库i和商店j的数字混乱，用n+j表示商店j
for(Re i=1;i<=n;++i)
for(Re j=1;j<=m;++j)
in(Cost[i][j]),add_(i,n+j,inf,Cost[i][j]);//仓库->商店
EK(st,ed);
printf("%lld\n",mincost);
memset(head,0,sizeof(head));
memset(cyf,0,sizeof(cyf));
memset(pre,0,sizeof(pre));
memset(a,0,sizeof(a));
o=1;maxflow=mincost=0;
for(Re i=1;i<=n;++i)add_(st,i,Flow[i][0],0);
for(Re i=1;i<=m;++i)add_(n+i,ed,Flow[i][1],0);
for(Re i=1;i<=n;++i)
for(Re j=1;j<=m;++j)
add_(i,n+j,inf,-Cost[i][j]);//变成负数后直接求得最大花费
EK(st,ed);
printf("%lld\n",-mincost);
}
```
------
### **2.【数字梯形问题】**
传送门：[数字梯形问题 $[P4013]$](https://www.luogu.org/problem/P4013) [$[Loj6010]$](https://loj.ac/problem/6010)
**（难度：简单）**
#### **【分析】**
三种不同拆点的实现。
将**最大流**人为设成 $m$，最后求一个最大流为 $m$ 的最大花费。
**【$Task$ $1$】**
每个点、每条边都只能经过一次。
$(1).$ **超源**与 $j \in [1,m]$ 连**流量为** $1$ **费用为** $0$ 的边。
$(2).$ $j \in [1,m+n-1]$ 与**超汇**连**流量为** $1$ **费用为** $0$ 的边。
$(3).$ 将点拆为**入点**和**出点**，连**流量为** $1$ **费用为数值**的边。
$(4).$ $i \in [1,n-1]$，$j\in [1,m+i-1]$ 与 $[i+1,j],[i+1,j+1]$ 都连流量为 $1$ 费用为 $0$ 的边。
**【$Task$ $2$】**
每个点可经过无数次，每条边只能经过一次。
在【$Task$ $1$】的基础上稍加修改即可。
$(1).$ $j \in [1,m+n-1]$ 与**超汇**连边**流量改为** $inf$ 。
$(2).$ 将点拆为**入点**和**出点**，连边**流量改为** $inf$ 。
**【$Task$ $3$】**
每个点、每条边都能经过无数次。
在【$Task$ $1$】的基础上稍加修改即可。
除了**超源**与 $j \in [1,m]$ 连的边，其他的**流量全部改为** $inf$ 。
#### **【Code】**
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=1200,M=1865,inf=2e9;//点数：(2m+n-1)*n/2*2+2=(3n-1)*n+2=1182 边数：1.5*n*n*3+m+m+n-1=4.5*n*n+3n=1860
int o=1,n,m,h,t,st,ed,O,Poi[23][43],A[23][43],cyf[N],pan[N],pre[N],dis[N],head[N];LL maxcost,maxflow;
struct QAQ{int w,to,next,flow;}a[M<<1];queue<int>Q;
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline void add(Re x,Re y,Re z,Re w){a[++o].flow=z,a[o].w=w,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void add_(Re a,Re b,Re flow,Re w){add(a,b,flow,w),add(b,a,0,-w);}
inline int SPFA(Re st,Re ed){
for(Re i=0;i<=ed;++i)dis[i]=-inf,pan[i]=0;
Q.push(st),pan[st]=1,dis[st]=0,cyf[st]=inf;
while(!Q.empty()){
Re x=Q.front();Q.pop();pan[x]=0;
for(Re i=head[x],to;i;i=a[i].next)
if(a[i].flow&&dis[to=a[i].to]<dis[x]+a[i].w){//求最大花费
dis[to]=dis[x]+a[i].w,pre[to]=i;
cyf[to]=min(cyf[x],a[i].flow);
if(!pan[to])pan[to]=1,Q.push(to);
}
}
return dis[ed]!=-inf;
}
inline void EK(Re st,Re ed){
while(SPFA(st,ed)){
Re x=ed;maxflow+=cyf[ed],maxcost+=(LL)cyf[ed]*dis[ed];
while(x!=st){
Re i=pre[x];
a[i].flow-=cyf[ed];
a[i^1].flow+=cyf[ed];
x=a[i^1].to;
}
}
}
inline void TAT1(){
for(Re i=1;i<=m;++i)add_(st,Poi[1][i],1,0);
for(Re i=1;i<=m+n-1;++i)add_(Poi[n][i]+O,ed,1,0);
for(Re i=1;i<=n;++i)
for(Re j=1;j<=m+i-1;++j){
add_(Poi[i][j],Poi[i][j]+O,1,A[i][j]);
if(i<n)add_(Poi[i][j]+O,Poi[i+1][j],1,0),
add_(Poi[i][j]+O,Poi[i+1][j+1],1,0);
}
EK(st,ed);
printf("%lld\n",maxcost);
}
inline void TAT2(){
for(Re i=1;i<=m;++i)add_(st,Poi[1][i],1,0);
for(Re i=1;i<=m+n-1;++i)add_(Poi[n][i]+O,ed,inf,0);//点数开放后，一个终点可以经过无数次
for(Re i=1;i<=n;++i)
for(Re j=1;j<=m+i-1;++j){
add_(Poi[i][j],Poi[i][j]+O,inf,A[i][j]);
if(i<n)add_(Poi[i][j]+O,Poi[i+1][j],1,0),
add_(Poi[i][j]+O,Poi[i+1][j+1],1,0);
}
EK(st,ed);
printf("%lld\n",maxcost);
}
inline void TAT3(){
for(Re i=1;i<=m;++i)add_(st,Poi[1][i],1,0);//全部开放后，起点仍然只能经过一次
for(Re i=1;i<=m+n-1;++i)add_(Poi[n][i]+O,ed,inf,0);
for(Re i=1;i<=n;++i)
for(Re j=1;j<=m+i-1;++j){
add_(Poi[i][j],Poi[i][j]+O,inf,A[i][j]);
if(i<n)add_(Poi[i][j]+O,Poi[i+1][j],inf,0),
add_(Poi[i][j]+O,Poi[i+1][j+1],inf,0);
}
EK(st,ed);
printf("%lld\n",maxcost);
}
inline void CL(){
memset(head,0,sizeof(head));
memset(cyf,0,sizeof(cyf));
memset(pre,0,sizeof(pre));
memset(a,0,sizeof(a));
maxflow=maxcost=0,o=1;
}
int main(){
in(m),in(n);
for(Re i=1;i<=n;++i)
for(Re j=1;j<=m+i-1;++j)
in(A[i][j]),Poi[i][j]=++O;
st=O<<1|1,ed=st+1;
TAT1(),CL(),TAT2(),CL(),TAT3();
}
```
------
### **3.【航空路线问题】**
传送门：[航空路线问题 $[P2770]$](https://www.luogu.org/problem/P2770) [$[Loj6122]$](https://loj.ac/problem/6122)
**（难度：中等）**
#### **【分析】**
题意：求从 $1$ 到 $n$ 两条互不相交的路径，使得经过的点数最大。
人为设定最大流为 $2$，节点数设为费用，最后求一个最大流为 $2$ 的最大花费。
$(1).$ 将点拆为**入点**和**出点**，连**流量为** $1$ **费用为** $1$ 的边。起点和终点特殊处理，连**流量为** $2$ **费用为** $1$ 的边。
$(2).$ 对于题目给定的边 $(x,y)$，将 $x$ 的**出点**与 $y$ 的**入点**相连。
完整题解：[【题解】【网络流24题】航空路线问题 $[P2770]$ $[Loj6122]$](https://www.luogu.org/blog/ChenXingLing/solution-p2770)
#### **【Code】**
```cpp
#include<algorithm>
#include<iostream>
#include<string>
#include<cstdio>
#include<queue>
#include<map>
#define LL long long
#define Re register int
using namespace std;
const int N=103,M=40000,inf=2e9;
int x,y,o=1,n,m,h,t,st,ed,flag,cyf[N],pan[N],pre[N],dis[N],head[N];LL maxcost,maxflow;
struct QAQ{int w,to,next,flow;}a[M<<1];queue<int>Q;string CH,ch[N];map<string,int>ip;
inline void add(Re x,Re y,Re z,Re w){a[++o].flow=z,a[o].w=w,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void add_(Re a,Re b,Re flow,Re w){add(a,b,flow,w),add(b,a,0,-w);}
inline int SPFA(Re st,Re ed){
for(Re i=0;i<=ed;++i)dis[i]=-inf,pan[i]=0;
Q.push(st),pan[st]=1,dis[st]=0,cyf[st]=inf;
while(!Q.empty()){
Re x=Q.front();Q.pop();pan[x]=0;
for(Re i=head[x],to;i;i=a[i].next)
if(a[i].flow&&dis[to=a[i].to]<dis[x]+a[i].w){//最大花费
dis[to]=dis[x]+a[i].w,pre[to]=i;
cyf[to]=min(cyf[x],a[i].flow);//最小残余网络
if(!pan[to])pan[to]=1,Q.push(to);
}
}
return dis[ed]!=-inf;
}
inline void EK(Re st,Re ed){
while(SPFA(st,ed)){
Re x=ed;maxflow+=cyf[ed],maxcost+=(LL)cyf[ed]*dis[ed];
while(x!=st){
Re i=pre[x];
a[i].flow-=cyf[ed];
a[i^1].flow+=cyf[ed];
x=a[i^1].to;
}
}
}
inline void dfs1(Re x){
pan[x]=1;//记录一下第一次选的点，第二次就不选它们了
cout<<ch[x-n]<<endl;//第一次正序输出。记得减n
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)<=n&&!a[i].flow){dfs1(to+n);break;}//出点x>n到入点to<=n,再从to的出点搜下去
}
inline void dfs2(Re x){
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)<=n&&!a[i].flow&&!pan[to+n])dfs2(to+n);//出点x>n到入点to<=n,再从to的出点搜下去
cout<<ch[x-n]<<endl;//第二次倒序输出。记得减n
}
int main(){
cin>>n>>m;st=1,ed=n<<1;
for(Re i=1;i<=n;++i)cin>>ch[i],ip[ch[i]]=i;
for(Re i=2;i<n;++i)add_(i,n+i,1,1);//1~n表示入点，n+1~2n表示出点
add_(1,1+n,2,1),add_(n,n+n,2,1);//起点和中点可以经过两次
while(m--){
cin>>CH;x=ip[CH];
cin>>CH;y=ip[CH];
if(x>y)swap(x,y);
flag|=x==1&&y==n;
add_(x+n,y,1,0);//刚从x的出点出来，接下来连到y的入点
}
EK(st,ed);
if(maxflow==2)printf("%d\n",maxcost-2);//找到了两条路
else if(maxflow==1&&flag){//只有一条从1直通n的边
printf("2\n");
cout<<ch[1]<<endl<<ch[n]<<endl<<ch[1]<<endl;//这里要输出三个
return 0;
}
else return !printf("No Solution!\n");
for(Re i=1;i<=n+2;++i)pan[i+n]=0;
dfs1(1+n),dfs2(1+n);//根据边的残余网络来判断是否选了该边，所以从出点开始搜，这里害我调了一个多小时
}
```
------
### **4.【深海机器人问题】**
传送门：[深海机器人问题 $[P4012]$](https://www.luogu.org/problem/P4012) [$[Loj6224]$](https://loj.ac/problem/6224)
**（难度：简单）**
#### **【分析】**
先把 $n,m$ 都加个 $1$ 。
有多个起点和终点，所以建立**超源和超汇**。
每条边可经过多次，但边权（费用）只会获得一次，用边流量来表示这个限制条件。
（另外，题目中说“*输入时横纵坐标要反过来*”是骗人的）
$(1).$ 对于每一个未到边界的坐标 $(i,j)$ 与 $[i+1,j],[i,j+1]$ 连一条**流量为** $1$ **费用为读入边权**的边。
$(2).$ 对于每一个未到边界的坐标 $(i,j)$ 与 $[i+1,j],[i,j+1]$ 连一条**流量为** $inf$ **费用为** $0$ 的边。
$(2).$ **超源**与给定坐标 $(x,y)$ 连**流量为读入当前坐标机器人数费用为** $0$ 的边。
$(3).$ 给定坐标 $(x,y)$ 与**超汇**连**流量为读入当前坐标机器人数费用为** $0$ 的边。
#### **【Code】**
```cpp
#include<algorithm>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=260,M=1540,inf=2e9;//点数: 16*16+2=258, 边数: 16*16*(4+2)=1536
int x,y,z,o=1,n,m,h,t,Q1,Q2,st,ed,cyf[N],pan[N],pre[N],dis[N],head[N];LL maxcost,maxflow;
struct QAQ{int w,to,next,flow;}a[M<<1];queue<int>Q;
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline void add(Re x,Re y,Re z,Re w){a[++o].flow=z,a[o].w=w,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void add_(Re a,Re b,Re flow,Re w){add(a,b,flow,w),add(b,a,0,-w);}
inline int SPFA(Re st,Re ed){
for(Re i=0;i<=ed;++i)dis[i]=-inf,pan[i]=0;
Q.push(st),pan[st]=1,dis[st]=0,cyf[st]=inf;
while(!Q.empty()){
Re x=Q.front();Q.pop();pan[x]=0;
for(Re i=head[x],to;i;i=a[i].next)
if(a[i].flow&&dis[to=a[i].to]<dis[x]+a[i].w){//最大花费
dis[to]=dis[x]+a[i].w,pre[to]=i;
cyf[to]=min(cyf[x],a[i].flow);
if(!pan[to])pan[to]=1,Q.push(to);
}
}
return dis[ed]!=-inf;
}
inline void EK(Re st,Re ed){
while(SPFA(st,ed)){
Re x=ed;maxflow+=cyf[ed],maxcost+=(LL)cyf[ed]*dis[ed];
while(x!=st){
Re i=pre[x];
a[i].flow-=cyf[ed];
a[i^1].flow+=cyf[ed];
x=a[i^1].to;
}
}
}
inline int Poi(Re x,Re y){return (x-1)*m+y;}
int main(){
in(Q1),in(Q2),in(n),in(m),++n,++m,st=n*m+1,ed=st+1;
for(Re i=1;i<=n;++i)
for(Re j=1;j<m;++j)
in(x),add_(Poi(i,j),Poi(i,j+1),1,x),add_(Poi(i,j),Poi(i,j+1),inf,0);
for(Re j=1;j<=m;++j)
for(Re i=1;i<n;++i)
in(x),add_(Poi(i,j),Poi(i+1,j),1,x),add_(Poi(i,j),Poi(i+1,j),inf,0);
while(Q1--)in(z),in(x),in(y),add_(st,Poi(x+1,y+1),z,0);//x,y要+1
while(Q2--)in(z),in(x),in(y),add_(Poi(x+1,y+1),ed,z,0);//x,y要+1
EK(st,ed);
printf("%lld",maxcost);
}
```
------
### **5.【汽车加油行驶问题】**
传送门：[汽车加油行驶 $[P4009]$](https://www.luogu.org/problem/P4009) [$[Loj6223]$](https://loj.ac/problem/6223)
**（难度：中等）**
#### **【分析】**
限制条件的转换：一份油可供汽车走一个单位长度，油箱最多可装 $K$ 份油。
贪心可知：
$(1).$ 每个坐标只会经过一次（虽然不会证明，但一直没有举出反例，而且这样子做能 $AC$ 姑且认为它是对的吧）。
$(2).$ 汽车只会在油用光时才自建加油站（这个是可以证明的，自己在草稿上举个例子看看就懂了）。
然后再说建模，可以用拆点实现**强制加油**，也可以不用，直接用**分层**所提供的天然优势进行**强制**操作即可。
$(1).$ 把每个坐标分为 $K+1$ 层，用第 $0$ 层表示满油状态，第 $1$ 层表示用掉了 $1$ 份油，第 $2$ 层表示用掉了 $2$ 份油 $...$ 第 $K$ 层表示油被用光的状态。
$(2).$ **超源**与第 $0$ 层的 $(1,1)$ 连**流量为** $1$ **费用为** $0$ 的边。
$(3).$ 将第 $k \in [1,K]$ 层的 $(n,n)$ 与**超汇**分别连**流量为** $1$ **费用为** $0$ 的边。
$(4).$ 对于有加油站的坐标 $(i,j)$，将第 $k \in [1,K]$ 层的 $(i,j)$ 与第 $0$ 层的 $(i,j)$ 连**流量为** $1$ **费用为** $A$ 的边，再第 $0$ 层的 $(i,j)$ 与上下左右四个方向坐标的第 $1$ 层分别连**流量为** $1$ 的边，当**向左**、**向上**时**费用为** $B$ ，反之**费用为** $0$ 。
$(4).$ 对于没有加油站的坐标 $(i,j)$，将第 $K$ 层的 $(i,j)$ 与 第 $0$ 层的 $(i,j)$ 连流量为 $1$ 费用为 $A+C$ 的边。将第 $k \in [0,K-1]$ 层的 $(i,j)$ 与上下左右四个方向坐标的第 $k+1$ 层分别连**流量为** $1$ 的边，**费用**同上。
$(5).$ 图中流量全为 $1$，可以直接跑最短路。
完整题解：[【题解】【网络流24题】汽车加油行驶问题 $[P4009]$ $[Loj6223]$](https://www.luogu.org/blog/ChenXingLing/solution-p4009)
#### **【Code】**
```cpp
#include<algorithm>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=11e4+5,M=6e5+5,inf=2e9;
int x,y,z,w,o=1,n,m,h,t,A,B,C,K,st,ed,cyf[N],pan[N],pre[N],dis[N],head[N];LL mincost,maxflow;
struct QAQ{int w,to,next,flow;}a[M<<1];queue<int>Q;
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline void add(Re x,Re y,Re z,Re w){a[++o].flow=z,a[o].w=w,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void add_(Re a,Re b,Re flow,Re w){add(a,b,flow,w),add(b,a,0,-w);}
inline int SPFA(Re st,Re ed){
for(Re i=0;i<=ed;++i)dis[i]=inf,pan[i]=0;
Q.push(st),pan[st]=1,dis[st]=0,cyf[st]=inf;
while(!Q.empty()){
Re x=Q.front();Q.pop();pan[x]=0;
for(Re i=head[x],to;i;i=a[i].next)
if(a[i].flow&&dis[to=a[i].to]>dis[x]+a[i].w){
dis[to]=dis[x]+a[i].w,pre[to]=i;
cyf[to]=min(cyf[x],a[i].flow);
if(!pan[to])pan[to]=1,Q.push(to);
}
}
return dis[ed]!=inf;
}
inline void EK(Re st,Re ed){
while(SPFA(st,ed)){
Re x=ed;maxflow+=cyf[ed],mincost+=(LL)cyf[ed]*dis[ed];
while(x!=st){
Re i=pre[x];
a[i].flow-=cyf[ed];
a[i^1].flow+=cyf[ed];
x=a[i^1].to;
}
}
}
inline int P(Re x,Re y,Re k){return (x-1)*n+y+k*n*n;}
int main(){
in(n),in(K),in(A),in(B),in(C),st=(K+1)*n*n+1,ed=st+1;//一共有(K+1)层
add_(st,P(1,1,0),1,0);//超级源点连到满油的起点
for(Re k=1;k<=K;++k)add_(P(n,n,k),ed,1,0);
//把每一层的终点连到超级汇点，所以第0层可以不连
for(Re i=1;i<=n;++i)
for(Re j=1;j<=n;++j){
in(x);
if(x){//已有加油站
for(Re k=1;k<=K;++k)add_(P(i,j,k),P(i,j,0),1,A);
//所有状态都必须花费A加油加到满，但由于不可能满油到达某一点，所以满油的第0层可以不加（连）
//加满油之后状态可以由满油状态到达K-1油的上下左右四个方向
if(i<n)add_(P(i,j,0),P(i+1,j,1),1,0);//横坐标+1,费用为0
if(j<n)add_(P(i,j,0),P(i,j+1,1),1,0);//纵坐标+1,费用为0
if(i>1)add_(P(i,j,0),P(i-1,j,1),1,B);//横坐标-1,费用为B
if(j>1)add_(P(i,j,0),P(i,j-1,1),1,B);//纵坐标-1,费用为B
}
else{//无加油站
for(Re k=0;k<K;++k){//从有油的状态到达下一层的四个方向
if(i<n)add_(P(i,j,k),P(i+1,j,k+1),1,0);//横坐标+1,费用为0
if(j<n)add_(P(i,j,k),P(i,j+1,k+1),1,0);//纵坐标+1,费用为0
if(i>1)add_(P(i,j,k),P(i-1,j,k+1),1,B);//横坐标-1,费用为B
if(j>1)add_(P(i,j,k),P(i,j-1,k+1),1,B);//纵坐标-1,费用为B
}
add_(P(i,j,K),P(i,j,0),1,A+C);//没有加油站的地方可以自给自足
}
}
EK(st,ed);
printf("%lld",mincost);
}
```
------
### **6.【孤岛营救问题】**
传送门：[孤岛营救问题 $[P4011]$](https://www.luogu.org/problem/P4011) [$[Loj6121]$](https://loj.ac/problem/6121)
**（难度：困难）**
#### **【分析】**
~~这是一道膜你题~~（$huaji$）
**坑点一：** **一个坐标可以有多把钥匙（这个是真的毒瘤）。**
**坑点二：** **每种钥匙都可以无限使用（玩魔塔玩多了会自然而然的以为一把钥匙只能用一次）。**
钥匙的拥有情况和门的存在都是限制条件，由于钥匙种类 $P$ 较小，可用二进制数压缩一下表示 $P$ 种钥匙的拥有情况。同 [$5.$ 汽车加油行驶](https://www.luogu.org/problem/P4009)，用 **分层**提供的不同状态来实现单点处获取钥匙。
$(1).$ **永远不可穿过**的墙所拦截的两点之间**不连边**。
$(2).$ 有钥匙的坐标就将**所有不包含该钥匙的状态**与**包含该钥匙的状态**连**流量为** $inf$ **费用为** $0$ 的边，然后将有钥匙的状态连出去，**流量为** $1$ **费用为 **$1$。
$(3).$ 可打开的门就找**包含了对应钥匙的状态**连边出去，**流量为** $inf$ **费用为** $1$ 的边。
最后，可以跑最大流为 $1$ 的最小费用，如果无法达到这个最大流就说明无解，也可以直接跑最短路。
#### **【Code】**
```cpp
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=2e5,M=2e6+5,inf=2e9;
int T,x,y,z,w,G,o=1,p,n,m,h,t,st,ed,maxp,cyf[N],pan[N],pre[N],dis[N],head[N],Map[11][11][11][11];LL mincost,maxflow;
struct QAQ{int w,to,next,flow;}a[M<<1];queue<int>Q;vector<int>key[11][11];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline void add(Re x,Re y,Re z,Re w){a[++o].flow=z,a[o].w=w,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void add_(Re a,Re b,Re flow,Re w){add(a,b,flow,w),add(b,a,0,-w);}
inline int SPFA(Re st,Re ed){
for(Re i=0;i<=ed;++i)dis[i]=inf,pan[i]=0;
Q.push(st),pan[st]=1,dis[st]=0,cyf[st]=inf;
while(!Q.empty()){
Re x=Q.front();Q.pop();pan[x]=0;
for(Re i=head[x],to;i;i=a[i].next)
if(a[i].flow&&dis[to=a[i].to]>dis[x]+a[i].w){
dis[to]=dis[x]+a[i].w,pre[to]=i;
cyf[to]=min(cyf[x],a[i].flow);
if(!pan[to])pan[to]=1,Q.push(to);
}
}
return dis[ed]!=inf;
}
inline void EK(Re st,Re ed){
while(SPFA(st,ed)){
Re x=ed;maxflow+=cyf[ed],mincost+=(LL)cyf[ed]*dis[ed];
while(x!=st){
Re i=pre[x];
a[i].flow-=cyf[ed];
a[i^1].flow+=cyf[ed];
x=a[i^1].to;
}
}
}
inline int P(Re x,Re y,Re k){return (x-1)*m+y+k*n*m;}
int main(){
in(n),in(m),in(p),maxp=(1<<p)-1;st=(maxp+1)*n*m+1,ed=st+1;
in(T);while(T--)in(x),in(y),in(z),in(w),in(G),Map[x][y][z][w]=Map[z][w][x][y]=G?G:-1;
in(T);while(T--)in(x),in(y),in(G),key[x][y].push_back(G);
add_(st,P(1,1,0),1,0);
for(Re k=0;k<=maxp;++k)add_(P(n,m,k),ed,1,0);
for(Re i=1;i<=n;++i)
for(Re j=1;j<=m;++j)
if(!key[i][j].empty())//有钥匙
for(Re O=0;O<key[i][j].size();++O){
Re KEY=key[i][j][O];
for(Re k=0;k<=maxp;++k){
if(!((k>>KEY-1)&1))add_(P(i,j,k),P(i,j,k|(1<<KEY-1)),inf,0);//这个状态没有这个钥匙
else{//这个状态有这个钥匙
if(i<n&&Map[i][j][i+1][j]!=-1){
if(!Map[i][j][i+1][j])add_(P(i,j,k),P(i+1,j,k),inf,1);
else if((k>>Map[i][j][i+1][j]-1)&1)add_(P(i,j,k),P(i+1,j,k),inf,1);
}
if(j<m&&Map[i][j][i][j+1]!=-1){
if(!Map[i][j][i][j+1])add_(P(i,j,k),P(i,j+1,k),inf,1);
else if((k>>Map[i][j][i][j+1]-1)&1)add_(P(i,j,k),P(i,j+1,k),inf,1);
}
if(i>1&&Map[i][j][i-1][j]!=-1){
if(!Map[i][j][i-1][j])add_(P(i,j,k),P(i-1,j,k),inf,1);
else if((k>>Map[i][j][i-1][j]-1)&1)add_(P(i,j,k),P(i-1,j,k),inf,1);
}
if(j>1&&Map[i][j][i][j-1]!=-1){
if(!Map[i][j][i][j-1])add_(P(i,j,k),P(i,j-1,k),inf,1);
else if((k>>Map[i][j][i][j-1]-1)&1)add_(P(i,j,k),P(i,j-1,k),inf,1);
}
}
}
}
else//无钥匙
for(Re k=0;k<=maxp;++k){
if(i<n&&Map[i][j][i+1][j]!=-1){
if(!Map[i][j][i+1][j])add_(P(i,j,k),P(i+1,j,k),inf,1);
else if((k>>Map[i][j][i+1][j]-1)&1)add_(P(i,j,k),P(i+1,j,k),inf,1);
}
if(j<m&&Map[i][j][i][j+1]!=-1){
if(!Map[i][j][i][j+1])add_(P(i,j,k),P(i,j+1,k),inf,1);
else if((k>>Map[i][j][i][j+1]-1)&1)add_(P(i,j,k),P(i,j+1,k),inf,1);
}
if(i>1&&Map[i][j][i-1][j]!=-1){
if(!Map[i][j][i-1][j])add_(P(i,j,k),P(i-1,j,k),inf,1);
else if((k>>Map[i][j][i-1][j]-1)&1)add_(P(i,j,k),P(i-1,j,k),inf,1);
}
if(j>1&&Map[i][j][i][j-1]!=-1){
if(!Map[i][j][i][j-1])add_(P(i,j,k),P(i,j-1,k),inf,1);
else if((k>>Map[i][j][i][j-1]-1)&1)add_(P(i,j,k),P(i,j-1,k),inf,1);
}
}
EK(st,ed);
if(maxflow)printf("%lld",mincost);
else printf("-1");
}
```
------
## **三：【参考文献】**
- [最详细（也可能现在不是了）网络流建模基础](https://www.cnblogs.com/victorique/p/8560656.html) （近乎完整的全套问题建模方法）
- [网络流 $24$ 题 题解](https://ksmeow.moe/graph_flow_24prob_sol/#toc-9)（经典网络流 $24$ 题全解）
------