↵
前几天，Libingyue2011 看到[此题](https://www.luogu.com.cn/problem/P1004)。↵
↵
woc，两条路径，还不让多取。↵
↵
于是大蒟蒻 Libingyue2011 不想写 dp 了，他觉得太难。↵
↵
又从一本蓝色的书上得知，此题可以用费用流，还能把加强版也顺带切了。↵
↵
于是，他就切了。↵
↵
所以，这其实是个网络流详解。↵
↵
# 网络流 1↵
↵
## 关于网络与流的一些知识 ↵
↵
一个网络是一张有向图，每条边都有一个权值 $c$。↵
↵
在网络中，有两个特殊节点，称为源点（$S$）与汇点（$T$）。↵
↵
$c(x,y)$ 为 $(x,y)$ 边的容量。↵
↵
定义函数 $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，~~因为下一个算法用,2026-02-10 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];↵
↵
Author: https://mirror.codeforces.com/profile/Libingyue20111 ↵
↵
This is the English version of the article. ↵
↵
[https://www.luogu.com.cn/article/kw6klidj](https://www.luogu.com.cn/article/kw6klidj)↵
↵
A few days ago, Libingyue2011 came across [this problem](https://www.luogu.com.cn/problem/P1004).↵
↵
Wow, two paths, and you can't collect the same point multiple times.↵
↵
So the novice Libingyue2011 didn't want to write dynamic programming (DP) anymore, as he found it too difficult.↵
↵
Then he learned from a blue-covered book that this problem could be solved using cost flow, and even the enhanced version could be solved along with it.↵
↵
So he solved it.↵
↵
Therefore, this is actually a detailed explanation of network flow.↵
↵
## Network Flow 1↵
↵
### Some Knowledge about Networks and Flows↵
A network is a directed graph where each edge has a weight $c$.↵
↵
In a network, there are two special nodes called the source ($S$) and the sink ($T$).↵
↵
$c(x,y)$ denotes the capacity of the edge $(x,y)$.↵
↵
Define the function $f(x,y)$ as the flow function of the edge $(x,y)$.↵
↵
It satisfies the following properties:↵
1. **Capacity Constraint**: $f(x,y) < c(x,y)$.↵
2. **Skew Symmetry**: $f(x,y) = -f(y,x)$.↵
3. **Flow Conservation**: For any node $x$ that is neither $S$ nor $T$, ↵
$\sum_{(u,x)} f(u,x) = \sum_{(x,v)} f(x,v)$, where $(u,x)$ and $(x,v)$ are edges in the graph.↵
↵
Due to the skew symmetry property, every edge in the network has a reverse edge.↵
↵
$c(x,y) - f(x,y)$ is called the residual capacity $\text{rest}(i,j)$ of an edge.↵
↵
The flow of a network is ↵
$\sum_{(S,v)} f(S,v)$, where $(S,v)$ are edges in the graph.↵
↵
A network flow can be likened to a pipeline system for transporting tap water: the source continuously produces water, the sink continuously stores water, and each intermediate node only transports water without storing it.↵
↵
There are many valid flow functions $f$ for a network. The flow function that maximizes the network's flow (as defined above) is called the **maximum flow**.↵
↵
[Maximum Flow Template Problem](https://www.luogu.com.cn/problem/P3376)↵
↵
### Edmonds-Karp Augmenting Path Algorithm↵
An augmenting path is a path from $S$ to $T$ where every edge has a residual capacity greater than 0.↵
↵
We can push an additional flow of $\min\operatorname{rest}(x,y)$ along this path, so the maximum flow increases by this value. ↵
For each edge $(x,y)$ on the path, its residual capacity $\operatorname{rest}(x,y)$ decreases by $\min\operatorname{rest}(x,y)$.↵
↵
Sometimes, some edges need to support inflows from other edges, so we don't necessarily have to reduce the residual capacity by the full $\min\operatorname{rest}(x,y)$.↵
↵
Would we have to use DFS, leading to exponential time complexity?↵
↵
Clever people came up with a solution: constructing reverse edges (flow retraction operation).↵
↵
When an augmenting path is found, we increase the residual capacity of the reverse edge $\operatorname{rest}(y,x)$ by $\min\operatorname{rest}(x,y)$.↵
↵
This allows for "regret" — if we find a better augmenting path that includes reverse edges, we can restore the residual capacity of the forward edges.↵
↵
This still satisfies the **flow conservation** property.↵
↵
This way, we can cancel out edges from suboptimal augmenting paths.↵
↵
By repeatedly finding and augmenting paths (with regret), we can find the maximum flow.↵
↵
#### How to Find Augmenting Paths?↵
BFS or DFS both work.↵
↵
However, I implemented BFS ~~because it's simpler~~.↵
↵
We keep updating the augmenting paths as long as we can find them, until no more augmenting paths exist.↵
↵
Time complexity: $O(nm^2)$ (proven on oi-wiki).↵
↵
In practice, it rarely reaches this upper bound for most networks.↵
↵
Thus, this algorithm can generally handle networks of scale $10^3 - 10^4$.↵
↵
**Code**:↵
```cpp↵
#include<bits/stdc++.h>↵
using namespace std;↵
#define int long long↵
int n,m,s,t;↵
// tot=1 to access reverse edges via XOR↵
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],pre[10010];↵
bool vis[10010];↵
↵
bool bfs(){↵
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];//最大流更新
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]){↵
// Skip if visited or no residual capacity↵
if(vis[to[i]] || !val[i]) continue;↵
// Find the minimum residual capacity on the path↵
dis[to[i]]=min(dis[u],val[i]);↵
// Record the edge to reconstruct the path↵
pre[to[i]]=i,vis[to[i]]=1;↵
q.push(to[i]);↵
// Early return if sink is reached↵
if(to[i]==t) return 1;↵
}↵
}↵
return 0;↵
}↵
↵
void update(){// Update the path↵
int x=t;↵
while(x!=s){↵
int i=pre[x];↵
val[i]-=dis[t];↵
// Update reverse edge using XOR↵
val[i^1]+=dis[t];↵
// Traverse back along the reverse edge↵
x=to[i^1];↵
}↵
// Update the maximum flow↵
maxflow+=dis[t];↵
}↵
↵
signed main() {↵
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 算法
for(int i=1;i<=m;i++){↵
int u,v,w;↵
cin>>u>>v>>w;↵
// Add forward edge and reverse edge (initial flow 0)↵
add(u,v,w),add(v,u,0);↵
}↵
// Augment until no more paths exist↵
while(bfs()) update();↵
cout<<maxflow;↵
return 0;↵
}↵
```↵
↵
### Dinic's Algorithm↵
The EK algorithm may traverse the entire residual network in one BFS but only finds one augmenting path.↵
↵
So how can we find multiple augmenting paths with a single BFS?↵
↵
We can use BFS to layer the graph, then use DFS on the layered graph (edges only go from layer $u$ to $u+1$) to find augmenting paths.↵
↵
Specifically: start from the source $S$, perform DFS down the layered graph to the sink $T$.↵
↵
When backtracking, update the augmenting path like EK, and check if a node can support the flow if it has multiple augmenting paths.↵
↵
#### Current Arc Optimization↵
This is the key reason Dinic is faster than EK.↵
↵
First, a node $u$ may be traversed multiple times.↵
↵
When enumerating edges of $u$, if the outgoing flow equals the incoming flow, return immediately — further updates would violate **flow conservation**.↵
↵
Thus, when we traverse $u$ the second time, we skip edges that have already been fully augmented.↵
↵
This optimization guarantees the time complexity.↵
↵
#### Why Layer the Graph?↵
First, the number of layers in the layered graph is at most the number of nodes $n$.↵
↵
As proven on oi-wiki, with the above optimizations, the time complexity of a single augmentation is $O(n)$ (where $n$ is the number of nodes).↵
↵
Total time complexity: $O(n^2m)$.↵
↵
In practice, it rarely reaches this upper bound for most networks.↵
↵
Thus, this algorithm can generally handle networks of scale $10^4 - 10^5$.↵
↵
**Note**: Without current arc optimization, the time complexity degrades to that of EK.↵
↵
**Code**:↵
```cpp↵
// Dinic's Algorithm↵
#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){↵
nxt[tot]=head[u];↵
nxt[tot]=head[u];↵
head[u]=tot;↵
}↵
int maxflow,dis[10010],now[10010];↵
bool vis[10010];↵
↵
bool bfs(){↵
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;↵
}↵
}↵
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;↵
// Reset current arc↵
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){↵
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 ↵
}↵
if(x==t) return flow;↵
// Remaining flow to push↵
int rest=flow;↵
// Enumerate edges (stop if rest=0)↵
for(int i=now[x];i && rest;i=nxt[i]){↵
// Current arc optimization↵
now[x]=i;↵
// Skip non-layered edges or edges with no residual capacity↵
if(dis[to[i]]!=dis[x]+1 || !val[i]) continue;↵
// Augment along the edge↵
int v=dinic(to[i],min(rest,val[i]));↵
// Prune: this path is no longer augmentable↵
if(!v) dis[to[i]]=0;↵
// Update residual capacity↵
val[i]-=v,val[i^1]+=v;↵
// Update remaining flow↵
rest-=v;↵
}↵
// Return the actual pushed flow↵
return flow-rest;↵
}↵
↵
signed main() {↵
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];
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;↵
// Augment until no more layered graphs↵
while(bfs()) ↵
// Augment all possible paths in the layered graph↵
while(flow=dinic(s,1e18)) ↵
maxflow+=flow;↵
cout<<maxflow;↵
return 0;↵
}↵
```↵
[Exercise](https://www.luogu.com.cn/problem/P1343)↵
↵
## Bipartite Graph 1↵
↵
### What is a Bipartite Graph?↵
**Definition 1**: An undirected graph where nodes can be divided into two disjoint sets such that no two nodes within the same set are adjacent. ↵
**Definition 2**: An undirected graph with no odd-length cycles.↵
↵
Thus, we can use a coloring algorithm to determine if a graph is bipartite and assign nodes to their respective sets.↵
↵
**Steps**:↵
1. For each node, if its adjacent nodes are uncolored, color them with a different color.↵
2. After coloring, use DFS to propagate the coloring.↵
3. If an adjacent node is already colored, check if it has a different color. If not, the graph is not bipartite.↵
4. Note: The graph may be disconnected.↵
↵
**Exercise**: [NOIP2010 Improvement Group] Imprisoning Criminals (https://www.luogu.com.cn/problem/P1525) (solve with binary search transformation).↵
↵
### Maximum Matching in Bipartite Graphs↵
The maximum number of edges that can be selected in a bipartite graph such that each node is incident to at most one selected edge.↵
↵
### Hungarian Algorithm↵
A simple algorithm for finding maximum matching in bipartite graphs.↵
↵
[Template: Maximum Matching in Bipartite Graphs](https://www.luogu.com.cn/problem/P3386)↵
↵
**Approach**:↵
- Represent left-set nodes as $u$ and right-set nodes as $v+n$.↵
- Although bipartite graphs are undirected, converting them to directed graphs (left to right) simplifies processing.↵
- For each left-set node, check if it can be matched to a right-set node without invalidating existing matches (we can reassign existing matches).↵
- Use DFS to implement this:↵
1. For a right-set node the left node can match to:↵
— If the right node is unmatched, match them directly.↵
— Otherwise, try to reassign the original left node paired with this right node.↵
2. Use a `vis` array to avoid reprocessing nodes in the same DFS call.↵
↵
**Code**:↵
```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;↵
}↵
// Matching of right-set nodes to left-set nodes↵
int mat[1010];↵
// Visited array for DFS↵
bool vis[1010];↵
↵
bool dfs(int x){↵
if(!vis[to[i]]){↵
vis[to[i]]=1;//vis 数组↵
if(!mat[to[i]] || dfs(mat[to[i]])){//满足二者之一↵
mat[to[i]]=x;//可行 ↵
return 1;↵
}↵
}↵
if(!vis[to[i]]){↵
vis[to[i]]=1;↵
// Either the right node is unmatched, or we can reassign its match↵
if(!mat[to[i]] || dfs(mat[to[i]])){↵
mat[to[i]]=x;↵
return 1;↵
}↵
}↵
return 0;↵
}↵
↵
int main() {↵
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 算法
for(int i=1;i<=e;i++){↵
int u,v;↵
cin>>u>>v;↵
add(u,v+n);↵
}↵
int ans=0;↵
// Iterate over left-set nodes↵
for(int i=1;i<=n;i++){↵
memset(vis,0,sizeof vis);↵
if(dfs(i)) ans++;↵
}↵
cout<<ans;↵
return 0;↵
}↵
```↵
Swapping the left and right sets yields the same answer.↵
↵
Time complexity: $O(nm)$ (traverse the entire graph $n$ times).↵
↵
### Dinic's Algorithm for Bipartite Matching↵
#### Conclusion 1↵
On unit-capacity networks, Dinic's algorithm has a time complexity of $O(m\min(\sqrt{m},n^{\frac{2}{3}}))$.↵
↵
#### Conclusion 2↵
On bipartite graphs with only unit-capacity edges, Dinic's time complexity is $O(m\sqrt{n})$.↵
↵
**Approach**:↵
1. Create virtual source $S$ and sink $T$.↵
2. Connect $S$ to all left-set nodes (capacity 1).↵
3. Connect all right-set nodes to $T$ (capacity 1).↵
4. The maximum flow of this network equals the maximum matching of the bipartite graph (easily proven).↵
↵
This solves bipartite matching in $O(m\sqrt{n})$ time.↵
↵
**Code**:↵
```cpp↵
// Dinic's Algorithm for Bipartite Matching↵
#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){↵
nxt[tot]=head[u];↵
nxt[tot]=head[u];↵
head[u]=tot;↵
}↵
int maxflow,dis[10010],now[10010];↵
bool vis[10010];↵
↵
bool bfs(){↵
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;↵
}↵
}↵
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){↵
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;↵
}↵
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() {↵
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↵
}↵
}↵
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);↵
}↵
// Connect source to left-set nodes↵
for(int i=1;i<=n;i++) add(0,i,1),add(i,0,0);↵
// Connect right-set nodes to sink↵
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;↵
}↵
```↵
↵
## Network Flow 2↵
↵
### Max-Flow Min-Cut Theorem↵
A **cut** of a network is a set of edges whose removal disconnects $S$ from $T$. The **min cut** is the cut with the smallest sum of edge capacities.↵
↵
**Theorem**: In any network, the maximum flow equals the min cut.↵
↵
**Proof**:↵
1. First, min cut $\ge$ max flow (if min cut $<$ max flow, an augmenting path still exists).↵
2. Let $A$ be the set of nodes reachable from $S$ in the residual network after finding the max flow, and $B$ be the unreachable set.↵
3. Max flow = total flow out of $S$ = total flow out of $A$ = total flow into $A$.↵
4. For any edge $(x,y)$ where $x \in A$ and $y \in B$:↵
— $(x,y)$ must be **saturated** (flow = capacity).↵
— For edge $(y,x)$, flow must be $0$ (otherwise, $(x,y)$ would have residual capacity $>0$).↵
5. The sum of capacities of all $(x,y)$ (from $A$ to $B$) equals the min cut (these edges disconnect $S$ from $T$).↵
6. Thus, min cut = max flow.↵
↵
Q.E.D.↵
↵
[Exercise](https://www.luogu.com.cn/problem/P1344)↵
↵
### Dinic's Algorithm Optimizations↵
[Template: Max Flow Enhanced Version / Preflow Push](https://www.luogu.com.cn/problem/P4722)↵
↵
I don't know what preflow push is. Let's try some "black magic" optimizations.↵
↵
#### Optimization 1: Bitwise Segmentation↵
Dinic's algorithm is slow when flow values vary significantly.↵
↵
**Approach**:↵
1. Split flow values into groups by binary bits: group $p$ contains values $2^p \le x < 2^{p+1}$.↵
2. Enumerate groups from largest to smallest, run Dinic on each group.↵
3. Keep edges from previous groups for subsequent runs.↵
↵
This reduces time complexity to $O(nm\log C)$ (proof omitted).↵
↵
**Code**:↵
```cpp↵
// Dinic with Bitwise Segmentation↵
#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 for layering↵
queue<int>q;// STL queue↵
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]);↵
// Early return if sink is reached↵
if(to[i]==t) return 1;↵
}↵
}↵
return 0;↵
}↵
↵
int dinic(int x,int 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;↵
}↵
int rest=flow;↵
for(int i=now[x];i && rest;i=nxt[i]){↵
now[x]=i;// Current arc optimization↵
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{↵
}e[120010];↵
↵
signed main() {↵
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，但参与更新
cin>>n>>m>>s>>t;↵
// Store edges first↵
for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w;↵
// Enumerate bits from highest to lowest↵
for(int i=30;i>=0;i--){↵
int p=(1<<i);↵
// Add edges in current group↵
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);↵
// Run Dinic and accumulate answer↵
int flow=0;↵
while(bfs()) ↵
while(flow=dinic(s,1e18)) ↵
maxflow+=flow;↵
// Keep edges for next groups↵
}↵
cout<<maxflow;↵
return 0;↵
}↵
```↵
Score: 68 pts (https://www.luogu.com.cn/record/169178727)↵
↵
#### Optimization 2: Reverse Edge Retention (Self-named)↵
Since Optimization 1 processes part of the graph first, we can extend this idea.↵
↵
Reverse edges impact efficiency (flow going back).↵
↵
**Approach**:↵
1. Run Dinic once without considering reverse edges (but track their weights).↵
2. Add reverse edges and run Dinic again.↵
↵
This significantly improves efficiency.↵
↵
**Code**:↵
```cpp↵
// Dinic with Reverse Edge Retention↵
#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){// Modified add function↵
to[++tot]=v,val[tot]=w;↵
nxt[tot]=head[u];↵
head[u]=tot;↵
// Store edges for Dinic↵
e[u].push_back(tot);↵
// Add reverse edge (not used in Dinic initially, but updated)↵
to[++tot]=u,val[tot]=0;↵
nxt[tot]=head[v];↵
head[v]=tot;↵
}↵
↵
int maxflow,dis[10010],now[10010];↵
bitset<10010>vis;↵
bool Flag=0;↵
int Q[10010],H,T;↵
↵
inline bool bfs(){↵
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;
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){↵
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;↵
}↵
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{↵
}E[120010];↵
↵
signed main() {↵
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 算法
cin>>n>>m>>s>>t;↵
for(int i=1;i<=m;i++) cin>>E[i].u>>E[i].v>>E[i].w;↵
// Enumerate bits↵
for(int i=30;i>=0;i--){↵
int p=(1<<i);↵
int kt=tot;↵
// Add edges in current group↵
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);↵
// First Dinic run (without reverse edges)↵
int flow=0;↵
while(bfs()) ↵
while(flow=dinic(s,1e18)) ↵
maxflow+=flow;↵
// Add reverse edges↵
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);↵
}↵
}↵
// Second Dinic run (with reverse edges)↵
while(bfs()) ↵
while(flow=dinic(s,1e18)) ↵
maxflow+=flow;↵
}↵
cout<<maxflow;↵
return 0;↵
}↵
```↵
Score: 84 pts (https://www.luogu.com.cn/record/169372193)↵
↵
#### Optimization 3: Bit Compression (Optimization for Optimization 1)↵
Process 3 bits at a time instead of 1. This reduces the number of iterations but increases the flow range per iteration.↵
↵
Efficiency depends on data, but this passes the problem.↵
↵
**Code**:↵
```cpp↵
// Dinic with Bit Compression (3 bits at a time)↵
#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){↵
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];↵
nxt[tot]=head[u];↵
head[u]=tot;↵
e[u].push_back(tot);↵
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(){↵
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;
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){↵
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;↵
}↵
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{↵
}E[120010];↵
↵
signed main() {↵
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↵
cin>>n>>m>>s>>t;↵
for(int i=1;i<=m;i++) cin>>E[i].u>>E[i].v>>E[i].w;↵
// Enumerate 3 bits at a time↵
for(int i=30;i>=0;i-=3){↵
int p=(1<<i);↵
int kt=tot;↵
// Add edges in current group (8x range)↵
for(int j=1;j<=m;j++) ↵
if(E[j].w>=p && E[j].w<p*8) ↵
add(E[j].u,E[j].v,E[j].w);↵
// First Dinic run↵
int flow=0;↵
while(bfs()) ↵
while(flow=dinic(s,1e18)) ↵
maxflow+=flow;↵
// Add reverse edges↵
for(int j=1;j<=m;j++){↵
if(E[j].w>=p && E[j].w<p*8){↵
kt+=2;↵
e[E[j].v].push_back(kt);↵
}↵
}↵
// Second Dinic run↵
while(bfs()) ↵
while(flow=dinic(s,1e18)) ↵
maxflow+=flow;↵
}↵
cout<<maxflow;↵
return 0;↵
}↵
```↵
AC Record: (https://www.luogu.com.cn/record/169372645)↵
↵
Time complexity: "black magic" (depends on data).↵
↵
[My Solution](https://www.luogu.com.cn/article/1jmnl3oj)↵
↵
### Cost Flow↵
[Template: Minimum Cost Maximum Flow](https://www.luogu.com.cn/problem/P3381)↵
↵
#### Edmonds-Karp Algorithm for Cost Flow↵
Replace BFS with SPFA to find the augmenting path with the minimum total cost.↵
↵
The cost of reverse edges is the negative of the forward edges.↵
↵
Code omitted (EK is too inefficient).↵
↵
Time complexity: $O(n^2m^2)$ (works for random data due to loose upper bound).↵
↵
#### Dinic's Algorithm for Cost Flow↵
Replace BFS layering with SPFA to find the shortest path in terms of cost.↵
↵
An edge $(u,v,w,cost)$ is part of the layered graph only if $dis_v = dis_u + cost$.↵
↵
Other logic is similar to standard Dinic.↵
↵
**Note**: Zero-cost cycles may cause infinite loops in DFS, so add a `vis` array to prevent this.↵
↵
**Code**:↵
```cpp↵
// Dinic's Algorithm for Minimum Cost Maximum Flow↵
#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 for cost-based layering↵
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;↵
// SLF optimization (search online for details)↵
if(dis[to[i]]<dis[q.empty() ? 0 :q.front()]) ↵
q.push_front(to[i]);↵
else ↵
q.push_back(to[i]);↵
}↵
}↵
}↵
// Clear vis for DFS↵
memset(vis,0,sizeof vis);↵
return dis[t]<dis[0]/2;↵
}↵
↵
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]+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;↵
if(x==t) return flow;// Reached sink↵
int rest=flow;↵
for(int i=now[x];i && rest;i=nxt[i]){↵
now[x]=i;↵
// Skip invalid edges or visited nodes↵
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];↵
// Update flow and cost↵
val[i]-=v,val[i^1]+=v,mincost+=cost[i]*v;↵
rest-=v;↵
}↵
vis[x]=1;↵
return flow-rest;↵
}↵
↵
struct node{↵
}e[100010];↵
↵
signed main() {↵
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];
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;↵
// Add edges (reverse edge cost is negative)↵
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);↵
int flow=0;↵
while(spfa()) ↵
while(flow=dinic(s,1e18)) ↵
maxflow+=flow;↵
cout<<maxflow<<" "<<mincost;↵
return 0;↵
}↵
```↵
Time complexity: $O(nmc)$.↵
↵
**Exercises**: [This Problem](https://www.luogu.com.cn/problem/P1004) and [Its Enhanced Version](https://www.luogu.com.cn/problem/P2045).↵
↵
**Important Notes**:↵
- Cost flow uses SPFA + DFS with a `vis` array, so avoid the "black magic" optimizations used for standard Dinic.↵
- Bitwise optimization leads to incorrect time complexity, and reverse edge retention leads to incorrect answers.↵
↵
## Bipartite Graph 2↵
↵
### Kőnig's Theorem↵
Kőnig's Theorem states that in bipartite graphs, the size of the minimum vertex cover equals the size of the maximum matching.↵
↵
A **minimum vertex cover** is the smallest set of nodes such that every edge is incident to at least one node in the set.↵
↵
The proof is analogous to the Max-Flow Min-Cut Theorem (omitted).↵
↵
### Maximum Independent Set in Bipartite Graphs↵
An **independent set** is a set of nodes with no edges between them.↵
↵
**Theorem**: The size of the maximum independent set in a bipartite graph equals the total number of nodes minus the size of the maximum matching.↵
↵
**Proof**:↵
- This is equivalent to removing the minimum number of nodes to eliminate all edges (minimum vertex cover).↵
- Thus, maximum independent set = total nodes — minimum vertex cover = total nodes — maximum matching.↵
↵
Q.E.D.↵
↵
### Weighted Matching in Bipartite Graphs↵
Weighted matching refers to finding the maximum matching with the maximum/minimum sum of edge weights.↵
↵
#### Cost Flow Solution↵
Solve it using cost flow like standard maximum matching (max flow with cost optimization).↵
↵
#### KM Algorithm↵
[Main Problem](https://www.luogu.com.cn/problem/P6577)↵
↵
Standard cost flow will not pass this problem — use KM instead.↵
↵
The KM algorithm solves weighted maximum matching for bipartite graphs with **perfect matching** (both sets have $n$ nodes, and maximum matching size is $n$).↵
↵
Here:↵
- Left-set nodes: $1$ to $n$.↵
- Right-set nodes: $n+1$ to $2n$.↵
↵
##### Vertex Labels↵
Denoted as $l$, a label for each node satisfying $l_x + l_y \ge w(x,y)$ for all edges $(x,y)$.↵
↵
##### Equality Subgraph↵
The subgraph consisting of all edges where $l_x + l_y = w(x,y)$.↵
↵
**Theorem**: If the equality subgraph contains a perfect matching of the original graph, this perfect matching is the maximum weight matching of the original graph.↵
↵
The total weight of this matching is $\sum_{i=1}^{2n} l_i$ (optimal since $l_x + l_y \ge w(x,y)$ for all edges).↵
↵
##### Alternating Tree↵
In the Hungarian algorithm, the tree traversed when a node fails to find a match is called an alternating tree (alternates between matched and unmatched edges).↵
↵
##### KM Algorithm Steps↵
1. Initialize labels:↵
- Left-set nodes: $l_i = \max\{w(i,j) | (i,j) \in E\}$.↵
- Right-set nodes: $l_i = 0$.↵
2. Expand the equality subgraph iteratively:↵
- Use the Hungarian algorithm to find matches in the equality subgraph.↵
- If a match fails, adjust labels:↵
- Subtract $\Delta$ from labels of all left-set nodes in the alternating tree.↵
- Add $\Delta$ to labels of all right-set nodes in the alternating tree.↵
- $\Delta = \min\{l_i + l_j - w(i,j) | i \in \text{alternating tree}, j \notin \text{alternating tree}\}$.↵
3. Optimization: Skip traversing previously visited alternating trees (time complexity reduces to $O(n^3)$).↵
↵
**Code**:↵
```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;↵
}↵
// Matching of right-set nodes to left-set nodes↵
int mat[1010];↵
bool vis[1010];↵
// Vertex labels, delta values, parent pointers↵
int l[1010],upd[1010],fa[1010];↵
↵
inline bool dfs(int x,int f){↵
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;↵
}↵
for(int i=head[x];i;i=nxt[i])↵
if(!vis[to[i]]){↵
// Edge is in equality subgraph↵
if(l[x]+l[to[i]]==val[i]){↵
vis[to[i]]=1,fa[to[i]]=f;↵
// Find a match↵
if(!mat[to[i]] || dfs(mat[to[i]],to[i])){↵
mat[to[i]]=x;↵
return 1;↵
}↵
}↵
// Update delta for non-equality edges↵
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(){↵
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];↵
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]);↵
}↵
// Process each left-set node↵
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;↵
// Try to find a match↵
if(dfs(mat[p],p)) break;↵
// Calculate delta↵
for(int j=n+1;j<=2*n;j++) ↵
if(!vis[j] && upd[j]<del) ↵
del=upd[j],p=j;↵
// Adjust labels↵
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;↵
}↵
// Update matching↵
while(p){↵
mat[p]=mat[fa[p]];↵
p=fa[p];↵
}↵
}↵
// Calculate total weight↵
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);↵
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 算法
for(int i=1;i<=e;i++){↵
int u,v,w;↵
cin>>u>>v>>w;↵
add(u,v+n,w);↵
}↵
cout<<KM()<<"\n";↵
// Output matching results↵
for(int i=1;i<=n;i++) cout<<mat[n+i]<<" ";↵
return 0;↵
}↵
```↵
↵
## Network Flow 3↵
↵
### Feasible Flow with Lower and Upper Bounds (No Source/Sink)↵
Given a network where each edge's flow is between $p(u,v)$ (lower bound) and $q(u,v)$ (upper bound), determine if a flow function exists that satisfies flow conservation for all nodes.↵
↵
**Approach**:↵
1. Naive idea: Use $q(u,v)-p(u,v)$ as edge capacities and set flow to $f(u,v)+p(u,v)$ — **incorrect** (lower bounds may not balance).↵
2. Correct approach:↵
— Create new source $S'$ and sink $T'$.↵
— Define:↵
— $inp(u) = \sum_{(i,u)} p(i,u)$ (total lower bound inflow to $u$).↵
— $outp(u) = \sum_{(u,i)} p(u,i)$ (total lower bound outflow from $u$).↵
— $d(u) = inp(u) - outp(u)$.↵
— If $d(u) > 0$: add edge $S' \to u$ with capacity $d(u)$.↵
— If $d(u) < 0$: add edge $u \to T'$ with capacity $-d(u)$.↵
— Run max flow from $S'$ to $T'$: feasible flow exists iff the flow is saturated (equals total $d(u) > 0$).↵
↵
### Feasible Flow with Lower and Upper Bounds (With Source/Sink)↵
Given a network where each edge's flow is between $p(u,v)$ and $q(u,v)$, determine if a flow function exists that satisfies flow conservation for all nodes except $S$ and $T$.↵
↵
**Approach**:↵
- Add an edge $T \to S$ with lower bound $0$ and upper bound $\infty$.↵
- Convert to the no-source/sink case (above).↵
- If feasible, the flow of the edge $T \to S$ equals the feasible flow from $S$ to $T$.↵
↵
### Maximum Flow with Lower and Upper Bounds (With Source/Sink)↵
1. Find a feasible flow using the above method.↵
2. Remove the edge $T \to S$ from the residual network.↵
3. Run max flow from $S$ to $T$ — total flow = feasible flow + max flow from step 3.↵
↵
### Minimum Flow with Lower and Upper Bounds (With Source/Sink)↵
1. Find a feasible flow using the above method.↵
2. Remove the edge $T \to S$ from the residual network.↵
3. Run max flow from $T$ to $S$ — total flow = feasible flow — max flow from step 3.↵
↵
**Note**: If all $d(u) = 0$, the minimum flow is $0$.↵
↵
**Code for U556791**:↵
```cpp↵
// Dinic for Flow with Lower/Upper Bounds↵
#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){↵
nxt[tot]=head[u];↵
nxt[tot]=head[u];↵
head[u]=tot;↵
}↵
int maxflow,dis[100010],now[100010];↵
bool vis[100010];↵
↵
bool bfs(){↵
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;↵
}↵
}↵
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){↵
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;↵
}↵
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() {↵
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;↵
}↵
```↵
↵
上下界网络流习题：↵
s=0,t=n+1;↵
for(int i=1;i<=m;i++){↵
int u,v,p,q;↵
cin>>u>>v>>p>>q;↵
// Add edge with capacity q-p↵
add(u,v,q-p),add(v,u,0);↵
// Update d(u) = inp — outp↵
V[u]-=p,V[v]+=p;↵
}↵
int sum=0;↵
bool flag=0;↵
// Add edges for lower bounds↵
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 edge T->S (infinite capacity)↵
add(T,S,1e15),add(S,T,0);↵
int flow=0;↵
// Check feasibility↵
while(bfs()) while(flow=dinic(s,1e18)) maxflow+=flow;↵
if(maxflow<sum) cout<<"A clever xzy~~~";↵
else{↵
// Save residual capacities↵
for(int i=1;i<=tot;i++) _val[i]=val[i];↵
// Calculate minimum flow (T->S max flow)↵
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 ";↵
// Calculate maximum flow (S->T max flow)↵
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;↵
}↵
```↵
↵
### Exercises for Flow with Lower/Upper Bounds↵
- [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)↵
↵
##
↵
并非上下界网络流。↵
↵
你可以将每条边的流量设为 $[L_i,R_i]$ 中的任意一个值 $x$。↵
↵
然后你就可以将这条边连为一条从 $u_i$ 到 $v_i$，流量为 $R_i-x$ 的边，和一条从 $v_i$ 到 $u_i$，流量为 $x-L_i$ 的边。↵
↵
当然 $inp$ 和 $outp$ 也要随之更改。↵
↵
这是网络流初值的任意性。↵
↵
## 上下界费用流↵
↵
考虑上下界流的过程，最开始将流量设为 $L_i$，接着再去考虑推流。↵
↵
所以只需将普通费用流最开始费用设为 $L_i\times c_i$ 就行了。↵
↵
## 有负环的费用流↵
↵
尝试转化一下，转化为无负环的。↵
↵
对于正常费用为正的边，正常处理。↵
↵
对于费用为负的边，可以利用网络流初值的任意性将边先满流。↵
↵
然后连边就是利用网络流任意性的方法连边，最后跑上下界网络流就行了。↵
↵
## 有负环的上下界费用流↵
↵
对于正常费用为正的边，正常处理。↵
↵
对于费用为负的边，可以利用网络流初值的任意性将边的流量设为 $R_i$。↵
↵
然后连边就是利用网络流任意性的方法连边，最后跑上下界网络流就行了。↵
↵
## 网络流应用（如何构建网络）↵
↵
有几个方法：↵
↵
1. 拆点，一般的将两个点拆为一个入点和一个出点。↵
↵
2. 利用费用流来控制形如前 $k$ 次走会有 $v$ 的贡献，后面走就没有贡献的。↵
↵
3. 商店和垃圾桶：可以设一个点为商店（排出流量），一个点为垃圾桶（收集流量），商店和垃圾桶不一定是源汇点。↵
↵
4. 最小割的建模一般都是选择一些东西，可以转化为使一些点不连通。（不希望割掉的边可以设为 inf）↵
↵
回到 [P1004](https://www.luogu.com.cn/problem/P1004)，我们来看下费用流如何建模↵
↵
首先，我们把每个点拆成一个入点和一个出点，这样尝试将点权转移到边权上。↵
↵
接着我们将每个点的入点连边出点，费用为点权，因为只能取一次，所以流量为 $1$。↵
↵
接着，因为每个点可以走 $2$ 次，所以再将每个点的入点连边出点，费用为 $0$，流量为 $1$。↵
↵
这就相当于每个点可以带费用的走一次，不带费用的走一次。↵
↵
剩下的就是相邻点出点连边入点。↵
↵
然后直接跑费用流即可。↵
↵
```cpp↵
//Dinic 算法
Not strictly flow with lower/upper bounds — arbitrary initial flow assignment:↵
1. For an edge with flow range $[L_i, R_i]$, set flow to arbitrary $x$.↵
2. Replace the edge with:↵
— Edge $u_i \to v_i$ with capacity $R_i - x$.↵
— Edge $v_i \to u_i$ with capacity $x - L_i$.↵
3. Update $inp$ and $outp$ accordingly (arbitrary initial flow property).↵
↵
### Cost Flow with Lower/Upper Bounds↵
1. Set initial flow to $L_i$ (lower bound).↵
2. Set initial cost to $L_i \times c_i$ (cost per unit flow).↵
3. Solve using standard cost flow.↵
↵
### Cost Flow with Negative Cycles↵
1. For edges with positive cost: process normally.↵
2. For edges with negative cost:↵
- Use arbitrary initial flow property to set flow to upper bound $R_i$.↵
- Replace edges as above.↵
3. Solve using flow with lower/upper bounds.↵
↵
### Cost Flow with Negative Cycles and Lower/Upper Bounds↵
1. For edges with positive cost: process normally.↵
2. For edges with negative cost:↵
- Set flow to upper bound $R_i$.↵
- Replace edges using arbitrary initial flow property.↵
3. Solve using flow with lower/upper bounds.↵
↵
### Applications of Network Flow (Graph Construction)↵
Key techniques:↵
1. **Node Splitting**: Split a node into an "in-node" and "out-node" (common for node capacity constraints).↵
2. **Cost Flow for Conditional Contributions**: Use cost flow to model contributions (e.g., first $k$ passes give $v$ reward, no reward afterward).↵
3. **Stores and Trash Bins**: Nodes as "stores" (produce flow) or "trash bins" (consume flow) — not necessarily source/sink.↵
4. **Min Cut Modeling**: Model selection problems as disconnecting nodes (set non-cuttable edges to $\infty$).↵
↵
### Back to P1004: Cost Flow Modeling↵
**Problem**: Two paths from top-left to bottom-right, no repeated point collection.↵
↵
**Modeling**:↵
1. **Node Splitting**: Split each node $(i,j)$ into in-node and out-node.↵
2. **Point Weight to Edge Weight**:↵
— Edge in-node $\to$ out-node: capacity $1$, cost = point weight (collect once).↵
— Edge in-node $\to$ out-node: capacity $1$, cost = $0$ (pass through again without collection).↵
3. **Adjacency Edges**: Connect out-node of $(i,j)$ to in-node of adjacent nodes (right/down).↵
4. Run cost flow (max flow = 2, max cost = total collected points).↵
↵
**Code**:↵
```cpp↵
// Dinic for P1004 (Cost Flow)↵
#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){↵
}↵
int maxflow,maxcost,dis[20010],now[20010];↵
bool vis[20010];↵
↵
bool spfa(){↵
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);↵
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;↵
q.push_back(to[i]);↵
}↵
}↵
}↵
memset(vis,0,sizeof vis);↵
return dis[t]>dis[0]/2;↵
}↵
↵
int dinic(int x,int flow){↵
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;↵
}↵
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{↵
}e[100010];↵
↵
namespace Input{↵
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){↵
void main() {↵
int u=0,v=0,w=0;↵
while(true){↵
cin>>u>>v>>w;↵
if(u==0 && v==0 && w==0) return;↵
a[u][v]=w;↵
}↵
}↵
}↵
↵
// Get node ID (in-node: k=0, out-node: k=1)↵
int get(int x,int y,int k){↵
return (x-1)*n+y+k*n*n;↵
}↵
↵
int k;↵
↵
signed main() {↵
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)。↵
↵
[例题](https://www.luogu.com.cn/problem/P4313)。↵
↵
尝试将转化为最小的删掉的贡献，转化为最小割问题。↵
↵
可以尝试建立源点 $S$ 代表选文科，汇点 $T$ 代表选理科。↵
↵
先处理 $art$ 和 $science$ 的满意度贡献。↵
↵
可以将 $S$ 连向点 $(i,j)$，边权为选文科的，$(i,j)$ 连向 $T$，边权为选理科的。↵
↵
接着处理 $same$ 产生的的满意度。↵
↵
可以对于每个点新建两个点来处理。↵
↵
我们将 $S$ 连向第一个点，边权为 $same_{art}$，再将那个点向那几个相邻点连边，边权为正无穷。↵
↵
我们将第二个点连向 $T$，边权为 $same_{science}$，再将那个点向那几个相邻点连边，边权为正无穷。↵
↵
这样，要让一个点与 $S$ 和 $T$ 不连通，必须割掉连接它与 $S$ 连的边或者它与 $T$ 连的边，因为 $same$ 用了一个虚点，必须让这里所有人把文科割了。↵
↵
所以这是正确的。↵
↵
```cpp↵
//Dinic 算法
cin>>n;↵
k=2;↵
s=1,t=2*n*n;↵
Input::main();↵
// Node splitting and edge creation↵
for(int i=1;i<=n;i++){↵
for(int j=1;j<=n;j++){↵
// Collect point (capacity 1, cost = point weight)↵
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]);↵
// Pass through (capacity k-1=1, cost 0)↵
add(get(i,j,0),get(i,j,1),k-1,0),add(get(i,j,1),get(i,j,0),0,0);↵
// Connect to down node↵
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);↵
// Connect to right node↵
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;↵
}↵
```↵
↵
**Exercise**: [P2045](https://www.luogu.com.cn/problem/P2045)↵
↵
**Example**: [P4313](https://www.luogu.com.cn/problem/P4313)↵
**Problem**: Maximize satisfaction by choosing arts/science for students (with group satisfaction).↵
↵
**Modeling**:↵
1. Source $S$ = choose arts, sink $T$ = choose science.↵
2. **Individual Satisfaction**:↵
— $S \to (i,j)$: capacity = art satisfaction (cut = lose art satisfaction).↵
— $(i,j) \to T$: capacity = science satisfaction (cut = lose science satisfaction).↵
3. **Group Satisfaction**:↵
— For art group satisfaction:↵
— Add virtual node $A_{i,j}$.↵
— $S \to A_{i,j}$: capacity = art group satisfaction.↵
— $A_{i,j} \to (i,j)$ and adjacent nodes: capacity = $\infty$ (must cut all if any node chooses science).↵
— For science group satisfaction:↵
— Add virtual node $B_{i,j}$.↵
— $B_{i,j} \to T$: capacity = science group satisfaction.↵
— $(i,j)$ and adjacent nodes $\to B_{i,j}$: capacity = $\infty$ (must cut all if any node chooses art).↵
4. Answer = total satisfaction — min cut.↵
↵
**Code**:↵
```cpp↵
// Dinic for P4313 (Min Cut)↵
#include<bits/stdc++.h>↵
using namespace std;↵
#define int long long↵
int n,m,s,t;↵
int head[30010],to[2000010],nxt[2000010],val[2000010],tot=1;↵
void add(int u,int v,int w){↵
nxt[tot]=head[u];↵
nxt[tot]=head[u];↵
head[u]=tot;↵
}↵
int maxflow,dis[30010],now[30010];↵
bool vis[30010];↵
↵
bool bfs(){↵
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();↵
// cout<<u<<"\n";↵
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;↵
}↵
}↵
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){↵
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;↵
}↵
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 ar[110][110],sc[110][110],sa[110][110],ss[110][110],S;↵
// Get node ID for (i,j)↵
inline int get(int i,int j){↵
}↵
signed main() {↵
cin>>n>>m;↵
s=0,t=3*n*m+1;↵
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){↵
cin>>ar[i][j];↵
S+=ar[i][j];↵
add(s,get(i,j),ar[i][j]),add(get(i,j),s,0);↵
}↵
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){↵
cin>>sc[i][j];↵
S+=sc[i][j];↵
add(get(i,j),t,sc[i][j]),add(t,get(i,j),0);↵
}↵
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){↵
cin>>sa[i][j];↵
S+=sa[i][j];↵
add(s,get(i,j)+n*m,sa[i][j]),add(get(i,j)+n*m,s,0);↵
add(get(i,j)+n*m,get(i,j),1e9),add(get(i,j),get(i,j)+n*m,0);↵
if(i>1) add(get(i,j)+n*m,get(i-1,j),1e9),add(get(i-1,j),get(i,j)+n*m,0);↵
if(j>1) add(get(i,j)+n*m,get(i,j-1),1e9),add(get(i,j-1),get(i,j)+n*m,0);↵
if(i<n) add(get(i,j)+n*m,get(i+1,j),1e9),add(get(i+1,j),get(i,j)+n*m,0);↵
if(j<m) add(get(i,j)+n*m,get(i,j+1),1e9),add(get(i,j+1),get(i,j)+n*m,0);↵
}↵
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){↵
cin>>ss[i][j];↵
S+=ss[i][j];↵
add(get(i,j)+2*n*m,t,ss[i][j]),add(t,get(i,j)+2*n*m,0);↵
add(get(i,j),get(i,j)+2*n*m,1e9),add(get(i,j)+2*n*m,get(i,j),0);↵
if(i>1) add(get(i-1,j),get(i,j)+2*n*m,1e9),add(get(i,j)+2*n*m,get(i-1,j),0);↵
if(j>1) add(get(i,j-1),get(i,j)+2*n*m,1e9),add(get(i,j)+2*n*m,get(i,j-1),0);↵
if(i<n) add(get(i+1,j),get(i,j)+2*n*m,1e9),add(get(i,j)+2*n*m,get(i+1,j),0);↵
if(j<m) add(get(i,j+1),get(i,j)+2*n*m,1e9),add(get(i,j)+2*n*m,get(i,j+1),0);↵
}↵
int flow=0;↵
while(bfs()) while(flow=dinic(s,1e18)) maxflow+=flow;↵
cout<<S-maxflow;↵
return 0;↵
}↵
```↵
↵
[例题](https://www.luogu.com.cn/problem/P2766)。↵
↵
遇到这种能取出多少个的，就可以考虑网络流了。↵
↵
第一问显然 dp 求解。↵
↵
第二问每个点只能用一次，可以考虑把每个点拆成入点和出点，然后入点连向出点一条流量为 $1$ 的边。↵
↵
因为这里取的是最长不下降子序列，我们发现，我们只用在 $dp$ 值为 $1$ 的地方开头，值为 $s$ 的地方结束就行了。↵
↵
于是建立源点 $S$ 汇点 $T$，将 $S$ 连向每个 $dp$ 值为 $1$ 的点，在所有 $dp$ 值为 $s$ 的地方连向 $T$。↵
↵
发现最长不下降子序列的转移必定是从 $dp_j=dp_i+1$ 的地方转移的，所以对于所有 $i<j$ 且 $a_i\le a_j$ 且 $dp_j=dp_i+1$ 的机房从 $i$ 的出点向 $j$ 的入点连边。↵
↵
这样就可以做第二问了。↵
↵
第三问我们只用将 $1$ 和 $n$ 的限制取消掉，就是将 $1$ 和 $n$ 的出入点之前的连边的流量变为正无穷。↵
↵
```cpp↵
//Dinic 算法 ↵
#include<bits/stdc++.h>↵
using namespace std;↵
#define int long long↵
int n,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]){↵
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 dp[10010],a[10010],ans;↵
signed main() {↵
cin>>n;↵
if(n==1){↵
cout<<"1\n1\n1";↵
return 0;↵
}↵
s=0,t=2*n+1;↵
for(int i=1;i<=n;i++){↵
cin>>a[i],dp[i]=1;↵
for(int j=1;j<i;j++) if(a[j]<=a[i]) dp[i]=max(dp[i],dp[j]+1);↵
ans=max(ans,dp[i]);↵
}↵
cout<<ans<<"\n";↵
for(int i=1;i<=n;i++) add(i,i+n,1),add(i+n,i,0);↵
for(int i=1;i<=n;i++) if(dp[i]==1) add(s,i,1),add(i,s,0);↵
for(int i=1;i<=n;i++) if(dp[i]==ans) add(i+n,t,1),add(t,i+n,0);↵
for(int i=1;i<=n;i++) for(int j=1;j<i;j++) if(a[j]<=a[i] && dp[i]==dp[j]+1) add(j+n,i,1),add(i,j+n,0);↵
int flow=0;↵
while(bfs()) while(flow=dinic(s,1e18)) maxflow+=flow;↵
cout<<maxflow<<"\n";↵
for(int i=2;i<=tot;i+=2) val[i]=val[i]+val[i^1],val[i^1]=0;↵
add(1,n+1,1e16),add(n+1,1,0),add(s,1,1e16),add(1,s,0);↵
if(dp[n]==ans) add(n,2*n,1e16),add(2*n,n,0),add(2*n,t,1e16),add(t,2*n,0);↵
maxflow=flow=0;↵
while(bfs()) while(flow=dinic(s,1e18)) maxflow+=flow;↵
cout<<maxflow<<"\n";↵
return 0;↵
}↵
```↵
↵
这后面可以还会更新吧。↵
↵
果然，在 2025/12/29 更新了一次。↵
↵
可以过几天又要更新，还有些内容没写完。
}↵
↵
signed main() {↵
cin>>n>>m;↵
s=0,t=3*n*m+1;↵
// Art satisfaction (S -> (i,j))↵
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){↵
cin>>ar[i][j];↵
S+=ar[i][j];↵
add(s,get(i,j),ar[i][j]),add(get(i,j),s,0);↵
}↵
// Science satisfaction ((i,j) -> T)↵
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){↵
cin>>sc[i][j];↵
S+=sc[i][j];↵
add(get(i,j),t,sc[i][j]),add(t,get(i,j),0);↵
}↵
// Art group satisfaction (virtual node)↵
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){↵
cin>>sa[i][j];↵
S+=sa[i][j];↵
add(s,get(i,j)+n*m,sa[i][j]),add(get(i,j)+n*m,s,0);↵
// Virtual node -> (i,j) (infinite capacity)↵
add(get(i,j)+n*m,get(i,j),1e9),add(get(i,j),get(i,j)+n*m,0);↵
// Connect to adjacent nodes↵
if(i>1) add(get(i,j)+n*m,get(i-1,j),1e9),add(get(i-1,j),get(i,j)+n*m,0);↵
if(j>1) add(get(i,j)+n*m,get(i,j-1),1e9),add(get(i,j-1),get(i,j)+n*m,0);↵
if(i<n) add(get(i,j)+n*m,get(i+1,j),1e9),add(get(i+1,j),get(i,j)+n*m,0);↵
if(j<m) add(get(i,j)+n*m,get(i,j+1),1e9),add(get(i,j+1),get(i,j)+n*m,0);↵
}↵
// Science group satisfaction (virtual node)↵
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){↵
cin>>ss[i][j];↵
S+=ss[i][j];↵
add(get(i,j)+2*n*m,t,ss[i][j]),add(t,get(i,j)+2*n*m,0);↵
// (i,j) -> virtual node (infinite capacity)↵
add(get(i,j),get(i,j)+2*n*m,1e9),add(get(i,j)+2*n*m,get(i,j),0);↵
// Connect adjacent nodes to virtual node↵
if(i>1) add(get(i-1,j),get(i,j)+2*n*m,1e9),add(get(i,j)+2*n*m,get(i-1,j),0);↵
if(j>1) add(get(i,j-1),get(i,j)+2*n*m,1e9),add(get(i,j)+2*n*m,get(i,j-1),0);↵
if(i<n) add(get(i+1,j),get(i,j)+2*n*m,1e9),add(get(i,j)+2*n*m,get(i+1,j),0);↵
if(j<m) add(get(i,j+1),get(i,j)+2*n*m,1e9),add(get(i,j)+2*n*m,get(i,j+1),0);↵
}↵
// Calculate min cut↵
int flow=0;↵
while(bfs()) while(flow=dinic(s,1e18)) maxflow+=flow;↵
// Answer = total satisfaction — min cut↵
cout<<S-maxflow;↵
return 0;↵
}↵
```
