题解 LZOJP3706 【搭配飞行员】
Hongse_Fox
·
·
个人记录
搭配飞行员·题解
这里先给一道类似但是有亮点的题：题目链接
这道题里面要求的是正飞行员和副飞行员的最大匹配
由于一个飞行员无法身兼两职所以我们可以把飞行员分成两个集合
满足任意两个匹配的人肯定分别在两个集合中
而不存在在一个集合中有两个匹配的人（真命题的逆否命题还是真命题）
于是这便是一道二分图最大匹配问题
这里给一些枯燥的定义：
匹配：
在图论中，一个匹配是一个边的集合，其中任意两条边都没有公共顶点
匹配边：
连接两个被匹配的点的边叫做匹配边
最大匹配：
一个图的匹配边数最多的匹配，称其为这个图的最大匹配
二分图的最大匹配：
在二分图中的最大匹配
而对于二分图最大匹配的问题一般网络流算法都会比匈牙利算法优秀
当然像 连续攻击游戏 那样的题匈牙利会好很多
而如果牵扯到匹配的费用那毫无疑问就要费用流了
网络最大流
（东西很多 建议先把模板背下来 也很好背）
所谓网络最大流这里只做一个简单的解说
举个形象生动的栗子
自来水厂通过一些管道给你家输水
这些管道有不同的粗细所以能通过的水流量是不一样的
而在一条水流的路径上最大的水流量总是等于最细读那个管子可以容纳的水流量
而最大流求的就是到你家的水流量之和最大可以是多少
那我们就先假装自己是个自来水厂小白来连一连
现在我们就按照能连就连的原则上
对于这个图上面的数字就是每条边的最大流量
我们现在从$S$走到$a$再从$a$走到$b$最后再从$b$走到$T
好第一条路就好了
但是我们再从S走到b之后发现没有路可以走了
于是我们就认为这个图的最大流是1
真是这样吗？
在上帝视角上我们发现这个图明明S->a->T和S->b->T这样子可以有2的流量
于是我们想反悔了 想让原来第一步a->b撤回去
于是反向边出场了
反向边（人没有后悔药 但边有）
所谓反向边顾名思义就是原来的边把方向反过来之后得到的边
它的作用只有一个 那就是帮你反悔
当我们在流的时候把管道减少的流量加到反向边那里
那么当我们再流反向边的时候其实就相当于没有流了
还是第一幅图（已经删去了第一次流完的流量并在ab之间建好了反向边）
现在我们又找到了一条路径S->b->a->T
在走完这条路之后结果和S->a->T+S->b->T就一样了
而且a->b的流量还是1（反向边的反向边还是它本身）
增广(FF \& dicnic)
现在万事具备只欠找可以流动路径了
像这种从源点到汇点并且路上所有的边都还有剩余流量的路径称为增广路
如果我们单纯地每次用dfs找一遍增广路
这便构成了我们最基础的网络流算法FF
但是这个算法有很大地优化空间：
具体就是当我们$dfs$到$u$时 对于$u$连接的所有点$v$都进行一次增广操作
最后增广的结果之和再返回给$u$的上一个节点
$2.$我们还可以对图按到汇点的最近距离进行分层（也可以按到源点）
分完层之后每次只往层数相差$1$的更低的地方进行增广
这样就可以避免混乱剩下很多时间
而处理距离只需要在增广之前进行一次$bfs$即可
如果$bfs$搜索不到源点就意味着没有增广路那就可以结束了
以上两点便构成了一个更优化的算法：**$dicnic$**
## $isap
上面的dicnic已经很优化了
但是我们发现每次dicnic之前要进行一次BFS操作很浪费时间
于是我们就用了isap
它只需要进行一次bfs操作一劳永逸 而在处理二分图的时候优势更明显
在上面的bfs中我们选择从汇点开始bfs
现在我们再从源点开始dfs
我们发现每次我们要重新bfs找dis实际上是因为有一些距离汇点比较远的点在原来的图内由于dis太大而一直没有遍历到
那这就很好解决了
我们每次dfs遍历完某个点后把它的dis++这样就终有一天可以把那些距离比较远大点给考虑进去了
这样就省下了很多次的bfs了
除此之外还有两个优化：
在$isap$中我们只可以向$dis$相差为一的流
那么一旦出现了断层即中间不存在某个值的$dis$那么源点就没办法流到汇点了
这样我们就可以拿一个$gap[i]$存一下$dis=i$的点的数量
一旦在我们进行$dis++$的操作之后原来的$gap[dis]=0$ 那么就说明原图已经没有增广路了
直接返回（在这里是$dis[s]=n$）
$2.cur$当前弧优化
在我们$dfs$的时候之前遍历过的点（边）肯定无法增广或者已经增广完了 那么我们就用一个$cur[i]$数组存下当前这个点$i$已经遍历到第几条边了 避免重复遍历
**code**
```cpp
inline int isap(int now,int nowflow){
if(now==t) return nowflow;//如果到了汇点就跑完了一条增广路
int sum=0;
for(register int i=cur[now];i;i=edge[i].next){//多路增广 注意当前弧优化
if(dis[edge[i].to]!=dis[now]-1 || (!edge[i].flow)) continue;//没流量的情况与dis优化
int akak=isap(edge[i].to,min(edge[i].flow,nowflow-sum));
//祝大家ak 注意比大小：剩下的nowflow以及这条边的流量取min
sum+=akak;cur[now]=i;//当前弧优化赋值
edge[i].flow-=akak;edge[fan(i)].flow+=akak;//当前边减反向边加
if(sum==nowflow || dis[s]==n) return sum;//如果当前流都流完了或者有断层就返回
}
gap[dis[now]]--;
if(!gap[dis[now]]) dis[s]=n;//出现了断层就结束
dis[now]++;gap[dis[now]]++;//当前dis++
cur[now]=head[now];//当前弧复位
return sum;
}
```
**二分图下由于图比较特殊可以不$bfs$直接改$dis,gap,cur$**
## 代码
```cpp
#include<cstdio>
#include<cctype>
#include<iostream>
using namespace std;
const int INF=0x7fffffff;
const int maxn=1e5+5;
inline int min(int a,int b){return a<b? a:b;}
inline int fan(int a){
if(a%2==0) return a-1;
return a+1;
}
inline int R(){
int r=0;char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) r=(r<<1)+(r<<3)+(c^48),c=getchar();
return r;
}
int a,b;
struct node{
int next,to,flow;
}edge[700005];
int n,n1,head[maxn],tot;
inline void add(int from,int to,int maxflow){
edge[++tot].next=head[from];
edge[tot].flow=maxflow;
edge[tot].to=to;
head[from]=tot;
return ;
}
int s,t,cur[maxn],gap[maxn],dis[maxn],ans;
inline int isap(int now,int nowflow){
if(now==t) return nowflow;//如果到了汇点就跑完了一条增广路
int sum=0;
for(register int i=cur[now];i;i=edge[i].next){//多路增广 注意当前弧优化
if(dis[edge[i].to]!=dis[now]-1 || (!edge[i].flow)) continue;//没流量的情况与dis优化
int akak=isap(edge[i].to,min(edge[i].flow,nowflow-sum));
//祝大家ak 注意比大小：剩下的nowflow以及这条边的流量取min
sum+=akak;cur[now]=i;//当前弧优化赋值
edge[i].flow-=akak;edge[fan(i)].flow+=akak;//当前边减反向边加
if(sum==nowflow || dis[s]==n) return sum;//如果当前流都流完了或者有断层就返回
}
gap[dis[now]]--;
if(!gap[dis[now]]) dis[s]=n;//出现了断层就结束
dis[now]++;gap[dis[now]]++;//当前dis++
cur[now]=head[now];//当前弧复位
return sum;
}
int main(){
n=R();n1=R();
s=1,t=n+2;
while(cin>>a>>b){
a++;b++;
add(a,b,1);
add(b,a,0);
}
dis[1]=3;gap[3]=1;//一堆初始化
dis[t]=0;gap[0]=1;
gap[2]=n1;gap[1]=n-n1;
for(register int i=2;i<=1+n1;i++){
dis[i]=2;
add(s,i,1);add(i,s,0);
}
for(register int i=n1+2;i<=n+1;i++){
dis[i]=1;
add(i,t,1);add(t,i,0);
}
n=t;//细节 我习惯n为点的总数
for(register int i=1;i<=n;i++){
cur[i]=head[i];//当前弧初始化
}
while(dis[s]<n) ans+=isap(s,INF);
printf("%d\n",ans);
return 0;
}
```
## 总结
网络最大流可以解决匹配问题
根据最大流等于最小割定理还可以解决最小割问题（看我的另一篇题解了）
这里给几道训练题：
$1.$方格取数问题（最大流等于最小割）
$2.$（洛谷）教辅的组成
$3.$shx的决斗
Finally，谢谢大家