网络流与二分图详解
MoonCake2011
·
·
算法·理论
前几天，Libingyue2011 看到此题。
woc，两条路径，TMD 还不让多取。
于是大蒟蒻 Libingyue2011 不想写 dp 了，他觉得太难。
又从一本蓝色的书上得知，此题可以用费用流，还能把加强版也顺带切了。
于是，他就切了。
所以，这其实是个网络流详解。
网络流 1
关于网络与流的一些知识
一个网络是一张有向图，每条边都有一个权值 c。
在网络中，有两个特殊节点，称为源点（S）与汇点（T）。
定义函数 $f(x,y)$ 为边 $(x,y)$ 的流函数。
它满足如下性质。
1. 容量限制：$f(x,y)<c(x,y)$。
2. 斜对称：$f(x,y)=-f(y,x)$。
3. 流量守恒：对于点 $x$ 不等于 $S$ 且不等于 $T$，满足 $\sum_{(u,x)}f(u,x)=\sum_{(x,v)}f(x,v)$，其中 $(u,x)$ 与 $(x,v)$ 都是图上的边。
由于有斜对称性质，其实网络中，每条边会有反向边的。
$c(x,y)-f(x,y)$ 被称为一条边的剩余容量 $\text{rest}(i,j)$。
一个网络的流量是 $\sum_{(S,v)}f(S,v)$，其中 $(S,v)$ 为图上的边。
一个网络流好比运输自来水的管道，在源点不停产生水，汇点不停的贮存水，每个节点不贮存水，只运输水。
其中，一个网络中，合法的流函数 $f$ 有很多，让那个网络的流量（上面说的）最大的流函数就是最大流。
[最大流模板题](https://www.luogu.com.cn/problem/P3376)。
## Edmonds-Karp 增广路算法
一条从 $S$ 到 $T$ 的每条边剩余容量都大于 $0$ 的路径。
可以多流 $\min\operatorname{rest}(x,y)$ 的流量，最大流可以加等于 $\min\operatorname{rest}(x,y)$，那路径上的所有边的 $\operatorname{rest}$ 需要减等于 $\min\operatorname{rest}(x,y)$。
其中 $(x,y)$ 在那条路径上。
有时我们有些边还需要支持其它边的流入，所以不一定要减满 $\min\operatorname{rest}(x,y)$。
难道要 `dfs`，变为指数级的吗？
聪慧的人想到一个办法，就是建反向边（退流操作）。
找到一条增广路，可以将反向边的剩余流量 $\operatorname{rest}(y,x)$ 的值加 $\min\operatorname{rest}(x,y)$。
这样就可以支持反悔，找到一条含反向边的增广路（更优的），就可以将正向边的剩余流量加回来。
且依旧满足**流量守恒**。
这样就可以抵消一些错误的增广路上的边。
这样不停增广，就能找到答案。（有反悔）
怎么找到增广路呢？
BFS，DFS，其实都行。
但是我写的是 BFS，~~因为下一个算法用 BFS 简单一点~~。
只要能找到增广路，就把增广路上的路径更新，直到没有增广路。
时间复杂度 $O(nm^2)$，oi-wiki 上可证。
但是在大多数网络上，它跑不太满。
所以一般此算法能处理 $10^3-10^4$ 规模的网络。
代码。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,s,t;
int head[10010],to[20010],nxt[20010],val[20010],tot=1;//这边 tot=1，使得反向边能用异或访问
void add(int u,int v,int w){
to[++tot]=v,val[tot]=w;
nxt[tot]=head[u];
head[u]=tot;
}
int maxflow,dis[10010],pre[10010];
bool vis[10010];
bool bfs(){
queue<int>q;
memset(vis,0,sizeof vis);
vis[s]=1,dis[s]=1e18;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=nxt[i]){
if(vis[to[i]] || !val[i]) continue;//如果访问过或流不动就 continue
dis[to[i]]=min(dis[u],val[i]);//找出增广路 min 值
pre[to[i]]=i,vis[to[i]]=1;//为了找出增广路
q.push(to[i]);
if(to[i]==t) return 1;//找到增广路了就直接 return
}
}
return 0;
}
void update(){//更新路径
int x=t;
while(x!=s){
int i=pre[x];
val[i]-=dis[t];
val[i^1]+=dis[t];//注意反向边，用异或访问
x=to[i^1];//反着走
}
maxflow+=dis[t];//最大流更新
}
signed main() {
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
add(u,v,w),add(v,u,0);//反向边最开始不流
}
while(bfs()) update();//只要有增广路，那就修改
cout<<maxflow;
return 0;
}
```
## Dinic 算法
EK 算法一次 BFS 有可能遍历整个残量网络，但是只能找出一条增广路。
于是我们怎么用一个 BFS，找到多条增广路。
可以用 BFS 将图分层，用 DFS 在分层图（只能从 $u$ 层流向 $u+1$ 层）上去寻找增广路。
详细的，就是从源点 $S$，在分层图上向下 `dfs` 到 $T$。
回溯时像 EK 一样更新增广路，注意看一下这个点如果有多条增广路，能否承受那么大的流量。
### 当前弧优化
重点来了，这就是 Dinic 比 EK 快的原因。
首先，一个点 $u$ 会被多次遍历。
每次枚举 $u$ 的边时，只要流出的流量等于流进的流量，直接 `return`。
因为再更新就不满足**流量守恒**了。
所以我们第二次遍历到 $u$ 的时候，就不用遍历那些增广完毕的边了。
这是保证复杂度的一个优化。
接着，下一个问题。
那为什么要分层呢？
首先，分层图上的层数小于等于点数 $n$。
在 oi-wiki 上有证明，用以上的东西可以证明单次增广的时间复杂度为 $O(n)$（$n$ 为点数）。
总时间复杂度 $O(n^2m)$。
但是在大多数网络上，它跑不太满。
所以一般此算法能处理 $10^4-10^5$ 规模的网络。
**注意，不加当前弧会将时间复杂度降低至 EK**。
代码。
```cpp
//Dinic 算法
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,s,t;
int head[10010],to[20010],nxt[20010],val[20010],tot=1;
void add(int u,int v,int w){
to[++tot]=v,val[tot]=w;
nxt[tot]=head[u];
head[u]=tot;
}
int maxflow,dis[10010],now[10010];
bool vis[10010];
bool bfs(){
queue<int>q;
memset(vis,0,sizeof vis);
vis[s]=1,dis[s]=0,now[s]=head[s];
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=nxt[i]){
if(vis[to[i]] || !val[i]) continue;
now[to[i]]=head[to[i]];//当前弧重置
dis[to[i]]=dis[u]+1,vis[to[i]]=1;
q.push(to[i]);
if(to[i]==t) return 1;
}
}
return 0;
}
int dinic(int x,int flow){
if(x==t) return flow;//到了汇点
int rest=flow;//维护流出量（这是流入量）
for(int i=now[x];i && rest;i=nxt[i]){//枚举，rest=0 时，不能再增广了
now[x]=i;//当前弧优化
if(dis[to[i]]!=dis[x]+1 || !val[i]) continue;//不是分层边或者剩余容量为 0，不行
int v=dinic(to[i],min(rest,val[i]));//增广
if(!v) dis[to[i]]=0;//这条路不能再增广，剪枝
val[i]-=v,val[i^1]+=v;//更新
rest-=v;//更新 rest
}
return flow-rest;
}
signed main() {
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
add(u,v,w),add(v,u,0);
}
int flow=0;
while(bfs()) while(flow=dinic(s,1e18)) maxflow+=flow;
cout<<maxflow;
return 0;
}
```
[习题](https://www.luogu.com.cn/problem/P1343)。
# 二分图 1
### 什么是二分图
判定 1：一张无向图，可以将图中点分为两类，同类间不连边。
判定 2：一张无向图中没有奇环。
所以说，我们可以通过染色法判断一张图是否为二分图，且找出一个点属于哪个点集。
具体的，对于每个点，如果与它相邻的点没有染色，就去染与这个点不同的颜色。
染了色后，去用 dfs 更新。
如果已经染了色，那么看一下是否与那个点是不同颜色的。
如果是，那此图不是二分图。
如不是，继续执行算法。
注意，图有可能不连通。
习题：[[NOIP2010 提高组] 关押罪犯](https://www.luogu.com.cn/problem/P1525)（用二分转化）。
### 二分图最大匹配
一个二分图最多选择的边数，使得每个点最多链接一条标记边。
### 匈牙利算法
匈牙利算法是一个处理二分图最大匹配的简单算法。
[【模板】二分图最大匹配](https://www.luogu.com.cn/problem/P3386)。
左部点描述成 $u$，右部点描述成 $v+n$。
虽然二分图是无向图，但化为有向图更好处理。
对于每条边，只从左部点连向右部点。
对于每个左部点，我们看一下能不能在不改变以前的人的匹配状态（可以改变匹配的右部点）的情况下，能否匹配到一个右部点。
于是直接开始 `dfs`。
对于一个它能匹配的右部点，看一下改变它能否可行。
这时候，如果它没有匹配的左部点，那么直接配上。
否则，就得改变它原来配对的左部点所配对的右部点。
`dfs` 就行了，注意 `vis` 数组要加。
代码。
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,e;
int head[1010],to[50010],nxt[50010],tot;
void add(int u,int v){
to[++tot]=v;
nxt[tot]=head[u];
head[u]=tot;
}
int mat[1010];
bool vis[1010];
bool dfs(int x){
for(int i=head[x];i;i=nxt[i])
if(!vis[to[i]]){
vis[to[i]]=1;//vis 数组
if(!mat[to[i]] || dfs(mat[to[i]])){//满足二者之一
mat[to[i]]=x;//可行
return 1;
}
}
return 0;
}
int main() {
cin>>n>>m>>e;
for(int i=1;i<=e;i++){
int u,v;
cin>>u>>v;
add(u,v+n);
}
int ans=0;
for(int i=1;i<=n;i++){//遍历左部点
memset(vis,0,sizeof vis);
if(dfs(i)) ans++;
}
cout<<ans;
return 0;
}
```
其实可以将左右点集交换，答案不变。
时间复杂度 $O(nm)$。（$n$ 次遍历全图）
### Dinic 算法
#### 结论 1
在单位容量的网络上，Dinic 算法时间复杂度是 $O(m\min(\sqrt{m},n^{\frac{2}{3}}))$。
#### 结论 2
在二分图上，只有单位容量的边，Dinic 时间复杂度 $O(m\sqrt{n})$。
我们又发现，将源点 $S$，与 $T$ 建为虚点。
$S$ 连所有左部点，所有右部点连 $T$。
发现在这个网络上跑网络流的答案就为二分图最大匹配的答案。
易证。
于是 $O(m\sqrt{n})$ 时间复杂度解决二分图匹配。
代码。
```cpp
//Dinic 算法
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,e,s,t;
int head[10010],to[200010],nxt[200010],val[200010],tot=1;
void add(int u,int v,int w){
to[++tot]=v,val[tot]=w;
nxt[tot]=head[u];
head[u]=tot;
}
int maxflow,dis[10010],now[10010];
bool vis[10010];
bool bfs(){
queue<int>q;
memset(vis,0,sizeof vis);
vis[s]=1,dis[s]=0,now[s]=head[s];
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=nxt[i]){
if(vis[to[i]] || !val[i]) continue;
now[to[i]]=head[to[i]];
dis[to[i]]=dis[u]+1,vis[to[i]]=1;
q.push(to[i]);
if(to[i]==t) return 1;
}
}
return 0;
}
int dinic(int x,int flow){
if(x==t) return flow;
int rest=flow;
for(int i=now[x];i && rest;i=nxt[i]){
now[x]=i;
if(dis[to[i]]!=dis[x]+1 || !val[i]) continue;
int v=dinic(to[i],min(rest,val[i]));
if(!v) dis[to[i]]=0;
val[i]-=v,val[i^1]+=v;
rest-=v;
}
return flow-rest;
}
signed main() {
cin>>n>>m>>e;
s=0,t=n+m+1;
for(int i=1;i<=e;i++){
int u,v;
cin>>u>>v;
add(u,v+n,1),add(v+n,u,0);
}
for(int i=1;i<=n;i++) add(0,i,1),add(i,0,0);
for(int i=1;i<=m;i++) add(i+n,n+m+1,1),add(n+m+1,i+n,0);
int flow=0;
while(bfs()) while(flow=dinic(s,1e18)) maxflow+=flow;
cout<<maxflow;
return 0;
}
```
# 网络流 2
## 最大流最小割定理
一个网络的割是一个边集，删掉那些边，会使 $S$ 与 $T$ 不连通。边的容量之和最小的割称为最小割
在任意一个网络中，最大流量等于最小割。
证明：
首先，最小割 $\ge$ 最大流，因为最小割 $<$ 最大流时，还可以找到增广路。
设在已求出最大流后的残量网络中，$S$ 可达点集为 $A$，不可达点集为 $B$。
最大流 $=$ 从 $S$ 流出的流量之和 $=$ 从 $A$ 流出的流量之和 $=$ 流入 $A$ 的流量之和。
如果 $x$ 在点集 $A$ 中，$y$ 在点集 $B$ 中，$(x,y)$ 是一条有向边，那么 $(x,y)$ 一定**满流**。
那如果 $(y,x)$ 是一条有向边，这些边的流量一定**为 $0$**，不然 $(x,y)$ 剩余容量大于 $0$。
于是，所有 $(x,y)$ 的容量之和，就为从 $A$ 流出的容量之和。
因为这些边可以使得 $S$ 与 $T$ 不连通。
所以最小割 $=$ 最大流。
证毕。
[习题](https://www.luogu.com.cn/problem/P1344)。
## Dinic 优化
[【模板】最大流 加强版 / 预流推进](https://www.luogu.com.cn/problem/P4722)。
预流推进是什么，我不道。
开始玄学优化。
### 优化 1，按位分段
Dinic 算法在流量差异大的时候跑的慢。
所以，可以将流量按二进制位分段。
将所有 $2^p \le x < 2^{p+1}$ 分为一组。
从大到小枚举组，去跑 Dinic。
将每次跑组跑完的边留下来，放到下一组接着跑。
这样时间复杂度能大大降低，变为 $O(nm\log C)$。
具体我不会证。
看代码。
```cpp
//Dinic 算法
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,s,t;
int head[10010],to[240010],nxt[240010],val[240010],tot=1;
void add(int u,int v,int w){
to[++tot]=v,val[tot]=w;
nxt[tot]=head[u];
head[u]=tot;
}
int maxflow,dis[10010],now[10010];
bool vis[10010];
bool bfs(){//BFS 分层
queue<int>q;//STL 队列
memset(vis,0,sizeof vis);
vis[s]=1,dis[s]=0,now[s]=head[s];
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=nxt[i]){
if(vis[to[i]] || !val[i]) continue;
now[to[i]]=head[to[i]];
dis[to[i]]=dis[u]+1,vis[to[i]]=1;
q.push(to[i]);
if(to[i]==t) return 1;//有增广路，直接 return
}
}
return 0;
}
int dinic(int x,int flow){
if(x==t) return flow;
int rest=flow;
for(int i=now[x];i && rest;i=nxt[i]){
now[x]=i;//当前弧优化
if(dis[to[i]]!=dis[x]+1 || !val[i]) continue;
int v=dinic(to[i],min(rest,val[i]));
if(!v) dis[to[i]]=0;
val[i]-=v,val[i^1]+=v;
rest-=v;
}
return flow-rest;
}
struct node{
int u,v,w;
}e[120010];
signed main() {
ios::sync_with_stdio(0);
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w;//存边
for(int i=30;i>=0;i--){//枚举位
int p=(1<<i);
for(int j=1;j<=m;j++) if(e[j].w>=p && e[j].w<p*2) add(e[j].u,e[j].v,e[j].w),add(e[j].v,e[j].u,0);//枚举边并加入，注意反向边
int flow=0;//跑 Dinic 并统计答案
while(bfs()) while(flow=dinic(s,1e18)) maxflow+=flow;//不删边，留到下一组接着跑
}
cout<<maxflow;
return 0;
}
```
有 [68 pts](https://www.luogu.com.cn/record/169178727)。
### 优化 2，反向滞留
~~这我自己取的名字~~。
你看，上一个优化都可以先跑一部分的图。
那这也可以。
发现反向边有点影响效率（人家跑过来的，你跑回去）。
于是先不算反向边跑一边 Dinic，但计算反向边的权值。
跑完后，直接加上反向边，再跑一次 Dinic。
发现效率大大提升。
代码。
```cpp
//Dinic 算法
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,s,t;
int head[10010],to[240010],nxt[240010],val[240010],tot=1;
vector<int>e[10010];
void add(int u,int v,int w){//注意 add 函数有变化
to[++tot]=v,val[tot]=w;
nxt[tot]=head[u];
head[u]=tot;
e[u].push_back(tot);//这里存的是要去跑 Dinic 的边
to[++tot]=u,val[tot]=0;
nxt[tot]=head[v];
head[v]=tot;//反向边先不参与 Dinic，但参与更新
}
int maxflow,dis[10010],now[10010];
bitset<10010>vis;
bool Flag=0;
int Q[10010],H,T;
inline bool bfs(){
H=1,T=0;
for(int i=1;i<=n;i++) vis[i]=0;
vis[s]=1,dis[s]=0,now[s]=0;
Q[++T]=s;
while(H<=T){
int u=Q[H++];
for(int i=0;i<e[u].size();i++){
if(vis[to[e[u][i]]] || !val[e[u][i]]) continue;
now[to[e[u][i]]]=0;
dis[to[e[u][i]]]=dis[u]+1,vis[to[e[u][i]]]=1;
Q[++T]=to[e[u][i]];
if(to[e[u][i]]==t) return 1;
}
}
return 0;
}
int dinic(int x,int flow){
if(x==t) return flow;
int rest=flow;
for(int i=now[x];i<e[x].size() && rest;i++){
now[x]=i;
if(dis[to[e[x][i]]]!=dis[x]+1 || !val[e[x][i]]) continue;
int v=dinic(to[e[x][i]],min(rest,val[e[x][i]]));
if(!v) dis[to[e[x][i]]]=0;
val[e[x][i]]-=v,val[e[x][i]^1]+=v;
rest-=v;
}
return flow-rest;
}
struct node{
int u,v,w;
}E[120010];
signed main() {
ios::sync_with_stdio(0);
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++) cin>>E[i].u>>E[i].v>>E[i].w;
for(int i=30;i>=0;i--){//下面与上面很不一样
int p=(1<<i);
int kt=tot;
for(int j=1;j<=m;j++)
if(E[j].w>=p && E[j].w<p*2)
add(E[j].u,E[j].v,E[j].w);//存边
int flow=0;//跑 Dinic
while(bfs()) while(flow=dinic(s,1e18)) maxflow+=flow;
for(int j=1;j<=m;j++){//加反向边
if(E[j].w>=p && E[j].w<p*2){
kt+=2;
e[E[j].v].push_back(kt);
}
}
while(bfs()) while(flow=dinic(s,1e18)) maxflow+=flow;//再跑一次
}
cout<<maxflow;
return 0;
}
```
有 [84 pts](https://www.luogu.com.cn/record/169372193)。
### 优化 3，对优化 1 的优化（压位优化）
将每次枚举一个二进制位变成三个二进制位，这样效率也许会高一些。
因为枚举次数会少，但是 Dinic 的值域增加。
所以效率因数据而定。
反正这样是过了。
代码。
```cpp
//Dinic 算法
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,s,t;
int head[1210],to[240010],nxt[240010],val[240010],tot=1;
vector<int>e[1210];
void add(int u,int v,int w){
to[++tot]=v,val[tot]=w;
nxt[tot]=head[u];
head[u]=tot;
e[u].push_back(tot);
// cout<<to[e[u][e[u].size()-1]]<<" "<<w<<"\n";
to[++tot]=u,val[tot]=0;
nxt[tot]=head[v];
head[v]=tot;
}
int maxflow,dis[1210],now[1210];
bitset<1210>vis;
bool Flag=0;
int Q[1210],H,T;
inline bool bfs(){
H=1,T=0;
for(int i=1;i<=n;i++) vis[i]=0;
vis[s]=1,dis[s]=0,now[s]=0;
Q[++T]=s;
while(H<=T){
int u=Q[H++];
for(int i=0;i<e[u].size();i++){
if(vis[to[e[u][i]]] || !val[e[u][i]]) continue;
now[to[e[u][i]]]=0;
dis[to[e[u][i]]]=dis[u]+1,vis[to[e[u][i]]]=1;
Q[++T]=to[e[u][i]];
if(to[e[u][i]]==t) return 1;
}
}
return 0;
}
int dinic(int x,int flow){
if(x==t) return flow;
int rest=flow;
for(int i=now[x];i<e[x].size() && rest;i++){
now[x]=i;
if(dis[to[e[x][i]]]!=dis[x]+1 || !val[e[x][i]]) continue;
int v=dinic(to[e[x][i]],min(rest,val[e[x][i]]));
if(!v) dis[to[e[x][i]]]=0;
val[e[x][i]]-=v,val[e[x][i]^1]+=v;
rest-=v;
}
return flow-rest;
}
struct node{
int u,v,w;
}E[120010];
signed main() {
ios::sync_with_stdio(0);
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++) cin>>E[i].u>>E[i].v>>E[i].w;
for(int i=30;i>=0;i-=3){//3位一次枚举
int p=(1<<i);
int kt=tot;
for(int j=1;j<=m;j++)
if(E[j].w>=p && E[j].w<p*8)//3位一次枚举
add(E[j].u,E[j].v,E[j].w);
int flow=0;
while(bfs()) while(flow=dinic(s,1e18)) maxflow+=flow;
for(int j=1;j<=m;j++){
if(E[j].w>=p && E[j].w<p*8){//3位一次枚举
kt+=2;
e[E[j].v].push_back(kt);
}
}
while(bfs()) while(flow=dinic(s,1e18)) maxflow+=flow;
}
cout<<maxflow;
return 0;
}
```
[AC 记录](https://www.luogu.com.cn/record/169372645)。
时间复杂度玄学。
[我的题解](https://www.luogu.com.cn/article/1jmnl3oj)。
## 费用流
[【模板】最小费用最大流](https://www.luogu.com.cn/problem/P3381)。
### Edmonds-Karp 算法
把 BFS 改为，用 SPFA 求一条费用之和最小的增广路。
建反边的费用为正边的相反数。
代码不给了，因为 EK 太低效了。
时间复杂度 $O(n^2m^2)$。
随机数据直接玄学，所以能过。
~~$n^2$ 过 $2.5\times 10^8$~~。
跑不满的。
### Dinic 算法
将用 BFS 分层改为用 SPFA 求费用之和的最短路。
一条边 $(u,v,w,cost)$ 为分层图的边仅当于 $dis_v=dis_u+cost$。
其他的于 Dinic 差不多。
因为图有时会有 $0$ 权环，所以会导致 Dinic 的 dfs 中陷入死循环。
所以加个 vis 数组。
代码。
```cpp
//Dinic 算法
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,s,t;
int head[10010],to[100010],nxt[100010],val[100010],cost[100010],tot=1;
void add(int u,int v,int w,int c){
to[++tot]=v,val[tot]=w,cost[tot]=c;
nxt[tot]=head[u];
head[u]=tot;
}
int maxflow,mincost,dis[10010],now[10010];
bool vis[10010];
bool spfa(){//spfa 分层
list<int>q;
memset(dis,0x3f,sizeof dis);
memset(vis,0,sizeof vis);
vis[s]=dis[s]=0,now[s]=head[s];
q.push_back(s);
while(!q.empty()){
int u=q.front();
q.pop_front();
vis[u]=0;
for(int i=head[u];i;i=nxt[i]){
now[to[i]]=head[to[i]];
if(!val[i]) continue;
if(dis[to[i]]>dis[u]+cost[i]){
dis[to[i]]=dis[u]+cost[i];
if(vis[to[i]]) continue;
vis[to[i]]=1;
if(dis[to[i]]<dis[q.empty() ? 0 :q.front()]) q.push_front(to[i]);
else q.push_back(to[i]);//SLF 优化，自己上网搜
}
}
}
memset(vis,0,sizeof vis);//清空 vis 留给 dfs
return dis[t]<dis[0]/2;
}
int dinic(int x,int flow){
vis[x]=1;//vis 数组
if(x==t) return flow;//其他一样
int rest=flow;
for(int i=now[x];i && rest;i=nxt[i]){
now[x]=i;
if(dis[to[i]]!=dis[x]+cost[i] || !val[i] || vis[to[i]]) continue;
int v=dinic(to[i],min(rest,val[i]));
if(!v) dis[to[i]]=dis[0];
val[i]-=v,val[i^1]+=v,mincost+=cost[i]*v;//注意更新费用
rest-=v;
}
vis[x]=1;
return flow-rest;
}
struct node{
int u,v,w,c;
}e[100010];
signed main() {
ios::sync_with_stdio(0);
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w>>e[i].c;
for(int i=1;i<=m;i++) add(e[i].u,e[i].v,e[i].w,e[i].c),add(e[i].v,e[i].u,0,-e[i].c);//反边的 cost 建相反数
int flow=0;
while(spfa()) while(flow=dinic(s,1e18)) maxflow+=flow;
cout<<maxflow<<" "<<mincost;
return 0;
}
```
时间复杂度：$O(nmc)$。
习题：[此题](https://www.luogu.com.cn/problem/P1004) 与 [此题的加强版](https://www.luogu.com.cn/problem/P2045)。
**注意：因为费用流是用的 SPFA + vis 数组的 dfs，所以与有些前面的 Dinic 玄学优化不一样，所以求费用流建议不用优化**。
**按位优化时复不正确，反向滞留答案不正确**。
# 二分图 2
## 二分图 Kőnig 定理
Kőnig 定理，是指二分图最小点覆盖等于最大匹配。
图的最小点覆盖，就是选一个点可以覆盖它旁边的所有边，覆盖所有边选择的最小点数。
发现证明等同于证明最大流最小割定理，证毕。
## 二分图最大独立集
图的独立集是在图中选出一定数量的点，使这些点中间没有边。
定理：二分图最大独立集为点数减去最大匹配数量。
证明：
这相当于就是去掉一些点，使剩下的点中没有边相连。
相当于就是二分图最小点覆盖。
证毕。
## 二分图带权匹配
二分图带权匹配，就是二分图最大匹配中选择边权之和最大 / 最小的。
### 费用流解法
可以直接像我们解最大匹配那样用费用流。
### KM 算法
[正片开始](https://www.luogu.com.cn/problem/P6577)。
想用正常的费用流跑的人可以洗洗睡了，过不去。
KM 算法可以解决在有**完备匹配**下的二分图带权匹配。
完备匹配是二分图左右都是 $n$ 个点且最大匹配为 $n$ 个点的匹配。
我这里以编号 $1$ 到 $n$ 的为左部点，$n+1$ 到 $2n$ 为右部点。
### 顶点标记值
简称顶标 $l$，一个点的顶标满足对于所有边 $l_x+l_y\ge w(x,y)$。
### 相等子图
所有 $l_x+l_y=w(x,y)$ 的边所构成的子图。
定理：如果相等子图存在原图的完备匹配，那么这个完备匹配就是二分图带权最大匹配。
此完备匹配的权值和为 $\sum_{i=1}^{2n} l_i$。
因为 $l_x+l_y\ge w(x,y)$，所以这一定最优。
### 交错树
在匈牙利算法中，从一个节点寻找然后匹配失败所遍历的树被称为交错树。
交错树一定是匹配边和非匹配边交错的，故得名。
~~大杂居，小聚居，交错居住。（bushi~~
### KM 算法流程
假设最开始左部点的 $l$ 为与它相连的边的权值最大值，右部点 $l$ 为 $0$。
就是尝试不断扩大相等子图。
先看一下普通的匈牙利算法流程，是每个点挨个遍历，然后用 `dfs` 判断是否能配。
我们的配对的过程中尝试去修改顶标。
尝试将交错树上所有左部点的顶标减去一个值 $\Delta$，右部点加上 $\Delta$。
对于一条匹配边，按照上面的方法修改，它绝对还是一个在相等子图里的边。
对于一条非匹配边，它的左部点如果减少 $\Delta$，那么右部点可能不增加 $\Delta$，而右部点 增加 $\Delta$，左部点必须减少 $\Delta$（因为交错树是由左部点访问的匈牙利算法弄出来的）。
于是所有非匹配边 $l_x+l_y$ 一定减少，所以说相等子图大小增加。
$\Delta$ 可以在所有 $i$ 在交错树里，$j$ 不在交错树里的边 $(i,j)$ 的 $l_i+l_j-w(i,j)$ 最小值作为 $\Delta$。
这样就可以完美达成条件。
于是时间复杂度就是 $O(n^2m)$ 的了。
接着，一个优化，就是之前遍历过的交错树可以不遍历（遍历相等子图里的没用），于是加上这个时间复杂度 $O(n^3)$ 的，可以过题。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,e;
int head[1010],to[250010],val[250010],nxt[250010],tot;
inline void add(int u,int v,int w){
to[++tot]=v,val[tot]=w;
nxt[tot]=head[u];
head[u]=tot;
}
int mat[1010];
bool vis[1010];
int l[1010],upd[1010],fa[1010];
inline bool dfs(int x,int f){
vis[x]=1;
for(int i=head[x];i;i=nxt[i])
if(!vis[to[i]]){
if(l[x]+l[to[i]]==val[i]){
vis[to[i]]=1,fa[to[i]]=f;
if(!mat[to[i]] || dfs(mat[to[i]],to[i])){
mat[to[i]]=x;
return 1;
}
}
else if(upd[to[i]]>l[x]+l[to[i]]-val[i]) upd[to[i]]=l[x]+l[to[i]]-val[i],fa[to[i]]=f;
}
return 0;
}
inline int KM(){
for(int i=1;i<=n;i++){
l[i]=-1e15,l[i+n]=0;
for(int j=head[i];j;j=nxt[j]) l[i]=max(l[i],val[j]);
}
for(int i=1;i<=n;i++){
memset(vis,0,sizeof vis);
memset(fa,0,sizeof fa);
memset(upd,0x3f,sizeof upd);
int p=0;mat[0]=i;
while(mat[p]){
int del=1e18;
if(dfs(mat[p],p)) break;
for(int j=n+1;j<=2*n;j++) if(!vis[j] && upd[j]<del) del=upd[j],p=j;
for(int j=1;j<=n;j++) if(vis[j]) l[j]-=del;
for(int j=n+1;j<=2*n;j++) if(vis[j]) l[j]+=del;else upd[j]-=del;
vis[p]=1;
}
while(p){
mat[p]=mat[fa[p]];
p=fa[p];
}
}
int ans=0;
for(int i=n+1;i<=2*n;i++) for(int j=head[mat[i]];j;j=nxt[j]) if(to[j]==i) ans+=val[j];
return ans;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>e;
for(int i=1;i<=e;i++){
int u,v,w;
cin>>u>>v>>w;
add(u,v+n,w);
}
cout<<KM()<<"\n";
for(int i=1;i<=n;i++) cout<<mat[n+i]<<" ";
return 0;
}
```
# 网络流 3
## 无源汇上下界可行流
对于一张网络，每条边的流量介于 $p(u,v)$ 与 $q(u,v)$ 之间，求使这张网络流量守恒的流函数是否存在。
首先聪明的大家都想着要去将 $q(u,v)-p(u,v)$ 跑最大流，这条边的流量就是跑出来的 $f(u,v)+p(u,v)$，但是这是错的。
$p(u,v)$ 可能不相等，所以这是错的。
为了调整，我们新建源点 $S'$ 和汇点 $T'$。
设一个点 $u$ 的 $inp(u)=\sum_{存在 (i,u) 这条边} p(i,u)$，$outp(u)=\sum_{存在 (u,i) 这条边} p(i,u)$，$d(u)=inp(u)-outp(u)$。
对于一个点 $u$，如果 $d(u) > 0$，$S'$ 向它连边，流量为 $d(u)$，如果 $d(u) < 0$，它向 $T'$ 连边，流量为 $-d(u)$。
接着从 $S'$ 到 $T'$ 跑最大流，如果满流，那么存在可行流，否则不存在。
## 有源汇上下界可行流
对于一张网络，每条边的流量介于 $p(u,v)$ 与 $q(u,v)$ 之间，求使这张网络除了 $S$ 和 $T$ 流量守恒的流函数是否存在。
可以将 $S$ 连到 $T$ 一条流量下界为 $0$，上界无限大的附加边，转化为无源汇上下界可行流。
若有解，则 $S$ 到 $T$ 的可行流流量等于 $T$ 到 $S$ 的附加边的流量。
## 有源汇上下界最大流
考虑在有源汇上下界可行流跑完的网络上调整。
于是在删去附加边的残量网络上再跑一次 $S$ 到 $T$ 的最大流（之前跑的是 $S'$ 和 $T'$ 的），将可行流加上最大流即是答案。
## 有源汇上下界最小流
考虑在有源汇上下界可行流跑完的网络上调整。
于是在删去附加边的残量网络上再跑一次 $T$ 到 $S$ 的最大流，将可行流减去最大流即是答案。
**注意：这里如果 $d(u)$ 全为 $0$ 那么最小流为 $0$，而不是上面算的**。
[U556791](https://www.luogu.com.cn/problem/U556791) 代码。
```cpp
//Dinic 算法
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,s,t,S,T;
int head[100010],to[100010],nxt[100010],val[100010],tot=1;
void add(int u,int v,int w){
to[++tot]=v,val[tot]=w;
nxt[tot]=head[u];
head[u]=tot;
}
int maxflow,dis[100010],now[100010];
bool vis[100010];
bool bfs(){
queue<int>q;
memset(vis,0,sizeof vis);
vis[s]=1,dis[s]=0,now[s]=head[s];
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=nxt[i]){
if(vis[to[i]] || !val[i]) continue;
now[to[i]]=head[to[i]];
dis[to[i]]=dis[u]+1,vis[to[i]]=1;
q.push(to[i]);
if(to[i]==t) return 1;
}
}
return 0;
}
int dinic(int x,int flow){
if(x==t) return flow;
int rest=flow;
for(int i=now[x];i && rest;i=nxt[i]){
now[x]=i;
if(dis[to[i]]!=dis[x]+1 || !val[i]) continue;
int v=dinic(to[i],min(rest,val[i]));
if(!v) dis[to[i]]=0;
val[i]-=v,val[i^1]+=v;
rest-=v;
}
return flow-rest;
}
int V[100010],_val[100010];
signed main() {
cin>>n>>m>>S>>T;
s=0,t=n+1;
for(int i=1;i<=m;i++){
int u,v,p,q;
cin>>u>>v>>p>>q;
add(u,v,q-p),add(v,u,0);
V[u]-=p,V[v]+=p;
}
int sum=0;
bool flag=0;
for(int i=1;i<=n;i++) if(V[i]>0) add(s,i,V[i]),add(i,s,0),flag=1,sum+=V[i];else if(V[i]<0) add(i,t,-V[i]),add(t,i,0),flag=1;
add(T,S,1e15),add(S,T,0);
int flow=0;
while(bfs()) while(flow=dinic(s,1e18)) maxflow+=flow;
if(maxflow<sum) cout<<"A clever xzy~~~";
else{
for(int i=1;i<=tot;i++) _val[i]=val[i];
s=T,t=S;
int ans=val[tot];
val[tot]=val[tot^1]=0;
maxflow=0;
while(bfs()) while(flow=dinic(s,1e18)) maxflow+=flow;
if(flag) cout<<ans-maxflow-1<<" ";else cout<<"-1 ";
swap(s,t);
for(int i=1;i<=tot;i++) val[i]=_val[i];
val[tot]=val[tot^1]=0;
maxflow=0;
while(bfs()) while(flow=dinic(s,1e18)) maxflow+=flow;
cout<<ans+maxflow+1;
}
return 0;
}
```
上下界网络流习题：
- [U556791](https://www.luogu.com.cn/problem/U556791)
- [P4043](https://www.luogu.com.cn/problem/P4043)
- [P4843](https://www.luogu.com.cn/problem/P4843)
- [P5192](https://www.luogu.com.cn/problem/P5192)
- [P5258](https://www.luogu.com.cn/problem/P5258)
拓展：
- [P4486](https://www.luogu.com.cn/problem/P4486)
## 网络流应用（如何构建网络）
回到 [P1004](https://www.luogu.com.cn/problem/P1004)，我们来看下费用流如何建模
首先，我们把每个点拆成一个入点和一个出点，这样尝试将点权转移到边权上。
接着我们将每个点的入点连边出点，费用为点权，因为只能取一次，所以流量为 $1$。
接着，因为每个点可以走 $2$ 次，所以再将每个点的入点连边出点，费用为 $0$，流量为 $1$。
这就相当于每个点可以带费用的走一次，不带费用的走一次。
剩下的就是相邻点出点连边入点。
然后直接跑费用流即可。
```cpp
//Dinic 算法
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,s,t;
int head[20010],to[100010],nxt[100010],val[100010],cost[100010],tot=1;
void add(int u,int v,int w,int c){
to[++tot]=v,val[tot]=w,cost[tot]=c;
nxt[tot]=head[u];
head[u]=tot;
}
int maxflow,maxcost,dis[20010],now[20010];
bool vis[20010];
bool spfa(){
list<int>q;
memset(dis,-0x3f,sizeof dis);
memset(vis,0,sizeof vis);
vis[s]=dis[s]=0,now[s]=head[s];
q.push_back(s);
while(!q.empty()){
int u=q.front();
q.pop_front();
vis[u]=0;
for(int i=head[u];i;i=nxt[i]){
now[to[i]]=head[to[i]];
if(!val[i]) continue;
if(dis[to[i]]<dis[u]+cost[i]){
dis[to[i]]=dis[u]+cost[i];
if(vis[to[i]]) continue;
vis[to[i]]=1;
// if(dis[to[i]]<dis[q.empty() ? 0 :q.front()]) q.push_front(to[i]);
// else q.push_back(to[i]);
q.push_back(to[i]);
}
}
}
memset(vis,0,sizeof vis);
return dis[t]>dis[0]/2;
}
int dinic(int x,int flow){
// cout<<x<<"\n";
vis[x]=1;
if(x==t) return flow;
int rest=flow;
for(int i=now[x];i && rest;i=nxt[i]){
now[x]=i;
if(dis[to[i]]!=dis[x]+cost[i] || !val[i] || vis[to[i]]) continue;
int v=dinic(to[i],min(rest,val[i]));
if(!v) dis[to[i]]=dis[0];
val[i]-=v,val[i^1]+=v,maxcost+=cost[i]*v;
rest-=v;
}
return flow-rest;
}
struct node{
int u,v,w,c;
}e[100010];
namespace Input{
int a[110][110];
void main() {
int u=0,v=0,w=0;
while(true){
cin>>u>>v>>w;
// cout<<u<<" "<<v<<" "<<w<<"\n";
if(u==0 && v==0 && w==0) return;
a[u][v]=w;
}
}
}
int get(int x,int y,int k){
return (x-1)*n+y+k*n*n;
}
int k;
signed main() {
ios::sync_with_stdio(0);
cin>>n;
k=2;
s=1,t=2*n*n;
Input::main();
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
add(get(i,j,0),get(i,j,1),1,Input::a[i][j]),add(get(i,j,1),get(i,j,0),0,-Input::a[i][j]);
add(get(i,j,0),get(i,j,1),k-1,0),add(get(i,j,1),get(i,j,0),0,0);
if(i<n) add(get(i,j,1),get(i+1,j,0),k,0),add(get(i+1,j,0),get(i,j,1),0,0);
if(j<n) add(get(i,j,1),get(i,j+1,0),k,0),add(get(i,j+1,0),get(i,j,1),0,0);
}
}
int flow=0;
while(spfa()) while(flow=dinic(s,1e18)) maxflow+=flow;
cout<<maxcost;
return 0;
}
```
[习题](https://www.luogu.com.cn/problem/P2045)。
这后面可以还会更新吧。