网络流
l1ng21y12026
·
·
算法·理论
网络流
（零）引入
定义集：
增广路：从S到T的一条路径上所有边的剩余容量>0；
最大流：从源点到达汇点的最大流量；
最小割：去除若干边使 S,T 不连通下的流量最小和；
最大流最小割定理：最大流=最小割；
（一）最大流
EK和Dinic的基本思想：不断寻找增广路使答案增大；
例题：【模板】最大流
给出一个网络图，以及其源点和汇点，求出其网络最大流。
对于 100\% 的数据，保证 1 \leq n\leq200，1 \leq m\leq 5000，0 \leq w\lt 2^{31}。
（1）EK（初步）
EK：时间复杂度O(nm^2)
每次Bfs一遍图，把找到的增广路上的容量减去当前增加的流量
（2）反向边
加上（1）即EK完整版
反向边：容量初始为0；当反向边与所对应的正向边的容量一个变化时，另一个变化量为其相反数
目的：从反向边流相当于取消了以前从正向边流过去
原因：一条边可以被包含在多条增广路中；计算一条增广路会改变容量从而影响其它增广路
如图，若Bfs遍历到的增广路为S,1,2,T，那么程序会认为就只有这一条增广路了
但显然：S,1,T；S,2,T两条增广路更优
观察加反向边后会怎么样
第一次bfs后：
然后奇妙的事情发生了，我们发现还有一条增广路：S,2,1,T
反向边就起到了交换的作用：将路径1和路径2的后半段交换，同时与所对边互相抵消
（3）Dinic
Dinic：时间复杂度O(n^2m)，处理二分图匹配时为O(m\sqrt n)
相比EK，增加了分层图优化，引入了dfs；每次只会搜到若干增广路上，不会像EK一样整个图跑一遍
算法流程：
1.Bfs求出每个点离S的距离dis[x]，同时确定还有没有增广路（每次走容量>0的边）遍历到T即有增广路
2.从dis\rightarrow dis+1，记录mn表示当前点的流量，递归求解，遍历到T返回流量；回溯时修改边的容量；
将mn减去给当前儿子的流量，剩下的考虑给下一个儿子
重复进行以上两个过程直到没有增广路
（4）优化
1.剪枝
回溯时：若子节点的增广路返回的流量为0，则该子节点不能流出增广路，将其dis设为inf。
2.当前弧优化
当dfs遍历到x的儿子j时，j前面的儿子都已经遍历过它们的增广路了；所以再遍历到x时从它第一个没有遍历过的儿子开始遍历。具体地，每次遍历儿子记录在now[x]上，每次遍历儿子时从now[x]遍历。
注意：每bfs一轮，now[x]=head[x]
#include<bits/stdc++.h>
#define int long long
#define rg register int
#define BZ printf("------\n");
#define frein freopen("in.txt","r",stdin);
#define freout freopen("out.txt","w",stdout);
#define fre(p) freopen(#p".in","r",stdin),freopen(#p".out","w",stdout);
#define outa(LL,RR,AA) {for(rg O=LL;O<=RR;O++)cout<<AA[O]<<" ";cout<<"\n";}
#define outm(LL1,RR1,LL2,RR2,AA) {for(rg U=LL1;U<=RR1;U++){for(rg V=LL2;V<=RR2;V++)cout<<AA[U][V]<<" ";cout<<"\n";}cout<<"\n";}
using namespace std;
void rd(int &num){
int v(0),op(1);
register char c=getchar();
while(c<'0'||'9'<c)op=c=='-'?-1:1,c=getchar();
while('0'<=c&&c<='9')v=(v<<1)+(v<<3)+(c^48),c=getchar();
num=v*op;
}
const int N=240005;
#define inf 1e14
int n,m,S,T,x,y,z,q[N],t,w,ans,dis[N];
int sum=1,now[N],hd[N],to[N],nex[N],v[N];
void add(int x,int y,int z){to[++sum]=y,nex[sum]=hd[x],v[sum]=z,hd[x]=sum;}
bool bfs(){
for(rg i=1;i<=n;i++)dis[i]=inf,now[i]=hd[i];
q[t=w=1]=S,dis[S]=0;
while(t<=w){
int x=q[t++];
for(rg i=hd[x];i>0;i=nex[i]){
int j=to[i];
if(v[i]>0&&dis[j]==inf){
q[++w]=j,dis[j]=dis[x]+1;
if(j==T)return 1;
}
}
}
return 0;
}
int dfs(int x,int mn){
if(x==T)return mn;
int k,res=0;
for(rg i=now[x];i>0&&mn>0;i=nex[i]){
int j=to[i];now[x]=i;
if(v[i]>0&&dis[j]==dis[x]+1){
k=dfs(j,min(mn,v[i]));
if(k==0)dis[j]=inf;
v[i]-=k,v[i^1]+=k,res+=k,mn-=k;
}
}
return res;
}
signed main(){
rd(n),rd(m),rd(S),rd(T);
for(rg i=1;i<=m;i++)rd(x),rd(y),rd(z),add(x,y,z),add(y,x,0);
while(bfs()==1)ans+=dfs(S,inf);
printf("%lld",ans);
return 0;
}
（二）最小割
标准的定义如下：
（1）求最小割
一个很重要的定理：最大流最小割定理，最大流=最小割；
于是可以直接用最大流求最小割。
（2）求最小割的点划分方案
可以从源点 S 开始 dfs，每次走残量 >0 的边，可以求出 S 点集的所有点。
void dfs(int x){
vis[x]=1;
for(rg i=hd[x];i;i=nex[i])if(vis[to[i]]==0&&v[i]>0)dfs(to[i]);
}
（3）求最少割边数量
先求出最小割，把没有满流的边容量改成 \infty，满流的边容量改成 1；
重新跑一遍最小割就可求出最小割边数量；
直接把所有边的容量设成 1，求一遍最小割就好了。
（三）最小费用最大流
例题：【模板】最小费用最大流
每条边都有费用，在最大流的情况下，使费用最小。
1 \leq n \leq 5\times 10^3$，$1 \leq m \leq 5 \times 10^4$，$1 \leq s,t \leq n$，$u_i \neq v_i$，$0 \leq w_i,c_i \leq 10^3
（1）EK
每次spfa出最小费用增广路，暴力回溯修改。
记录一下最优路径的上一个点，和边的编号即可。
（2）Dinic
一样的，把 bfs 换成 spfa 即可。
注意 dfs 要判是否重复进入一个点，需要 vis；spfa 的队列长度要开大一点。
void ado(int x,int y,int f,int c){to[++sum]=y,nex[sum]=hd[x],hd[x]=sum,ef[sum]=f,ec[sum]=c;}
void add(int x,int y,int f,int c){ado(x,y,f,c),ado(y,x,0,-c);}//ck(x,y,f,c);}
int sf,sc,t,w,q[M<<3],cur[N],dis[N];
bool vis[N];
bool bfs(){
fo(i,1,T)dis[i]=inf,cur[i]=hd[i],vis[i]=0;
q[t=w=1]=S,dis[S]=0,vis[S]=1;
while(t<=w){
int x=q[t++];vis[S]=0;
fe(i,x)if(ef[i]&&dis[to[i]]>dis[x]+ec[i]){
dis[to[i]]=dis[x]+ec[i];
if(vis[to[i]]==0)q[++w]=to[i];
}
}return dis[T]!=inf;
}
int dfs(int x,int fl){
if(x==T)return fl;
int s=0,t;vis[x]=1;
for(rg i=cur[x];i&&fl;i=nex[i]){
cur[x]=i;
if(ef[i]&&dis[to[i]]==dis[x]+ec[i]&&vis[to[i]]==0){
t=dfs(to[i],min(fl,ef[i]));
if(t==0)dis[to[i]]=inf;
ef[i]-=t,ef[i^1]+=t,s+=t,fl-=t,sc+=t*ec[i];
}
}vis[x]=0;return s;
}
sf=0,sc=0;
while(bfs())sf+=dfs(S,inf);
（四）二分图匹配
匈牙利算法；
遍历 1\sim n 看一下能不能匹配，直接暴力 dfs，调整法；
bool vis[M];int p[M];
bool dfs(int x){
fe(i,x)if(vis[to[i]]==0){
vis[to[i]]=1;
if(p[to[i]]==0||dfs(p[to[i]])==1){
p[to[i]]=x;
return 1;
}
}return 0;
}
（五）上下界网络流
咕
（六）最大权闭合子图
闭合子图：闭合图 G 中的点能到的点都必须属于 G。
它可以描述“选一个点就必须选一些点” 的限制。
例题：P2805 [NOI2009] 植物大战僵尸。
它的限制就是若植物 x 保护植物 y，那么取 y 必取 x。
那么怎么建图呢？我们可以将 (y\rightarrow x)。这样问题就变成了选一个闭合子图。
然后再考虑增加贡献，可以采用最小割的方法，把正权点连在 S，负权点连在 T，流量为权值的绝对值。
先算上正权点的贡献，当一个正权点和负权点相连，就用最小割的方式决策。
这样就可以了。
（七）最小路径覆盖
最小路径覆盖：若路径集合 P 恰好将有向图的每个点覆盖一次。则合法的 |P| 即为最小路径覆盖。
P2764 最小路径覆盖问题：DAG 简单不交路径覆盖。
路径数 = 点数 - 路径上边数。
建图：拆为入点、出点，图上有向边 x\to y 连 in_x\to out_y。那么图的最大匹配即最大的路径上的边数。即最小路径数。
求方案：检查反向边，若这条边被反向了，那么它被选了。由于是个有向路径，记录 pre[x] 表示 x 在路径上上一个点是什么即可。最后从入度为 0 的点用 pre 反向遍历可得路径。
[ABC374G] Only One Product Name：有向图不简单可交路径覆盖。
一个环显然可以被一并覆盖，故先缩点。
一个点可以被经过多次，可以传递闭包，即若 x\to y,y\to z，则加上边 x\to z，简单 floyd 实现。
剩下的按照上面的网络流即可。
（Last）应用与习题
网络流有很多经典问题。
（1）最小割刻画选择性
利用最小割，巧妙利用割边代表选择。
- 条件或：将两条边 a,b 串联成路径，表示要么割 a，要么割 b。
- 条件与：将两条边 a,b 并联到一个虚点上，表示 a,b 必须都割掉才能使路径不连通。
对了快去看文理分科的逻辑推导。
CF311E Biologist
题面
有一个长度为 n 的 01 串，将第 i 个位置取反的代价为 v_i。
有 m 个要求，每个要求指定 k_i 个位置，要求这些位置上的数都是 op=\{0,1\}。
如果满足了某个要求，你会获得 w_i 的收益。
对于 is=1 的要求，若不能满足，收益 -g。求最大收益。
题解
首先对于 $is=1$ 的要求，可以将满足收益 $+g$，总收益 $-g$。
发现是一个二选一模型，考虑求解。
我们**将割边与放弃要求、修改序列相联系**，对于一个要求：
- 要么我割断所有改变 0 和 1 的边来满足它；
- 要么我放弃这个要求，割断它的价值边；
这样，我们的思路就**从“满足”变成了“放弃”**；于是答案用 $\sum w_i-MinCut$ 计算。
现在来建图：
我们要达到的效果是：
- 割掉这条边，意味着**修改这个点，承担修改的代价**；
- 对于一个询问，需要**割掉它要求中需要改变的点的边**并且不割它的价值边，才能**使 $S,T$ 不连通**；
- 否则，**割掉它的价值边，代表放弃价值**。
于是，对于 0 的点，将 $S$ 连向它；对于 1 的点，将它连向 $T$；
再考虑如何满足第 2 个效果。
举个例子：
如果一个要求，价值为 $1$，要求 1,2 点都是 0；其中 1 点本来是 0；2 点本来是 1。
于是需要满足：割掉 2 点的边才能使图不连通。
而 2 点的边是连向 $T$ 的，可以对要求建一个点 $A$；
将 $S$ 连向 $A$，流量为要求的价值 $w$；再将它连向 2 点，流量为 $\infty$。
此处的 $\infty$ 是为了不让算法割掉这条边。
这样就构成了一条 $S\rightarrow A\rightarrow 2\rightarrow T$ 的路径；
要么割掉 $(S,A)$，不要价值 $w=1$；要么割掉 $(2,T)$，承担代价 $v_2$；
而对于 1 点，将 $A$ 连向 1 点，此时割 1 点不能使 $S,T$ 不连通，故满足要求。
对于要求变成 1 的要求，就是将它 ( $B,w=2$ ) 连向 $T$，流量为价值；
将选择的点连向 $B$，流量为 $\infty$；
这样对于本来是 0 的点 ( 1 )，就构成了一条 $S\rightarrow 1\rightarrow B\rightarrow T$ 的路径。
同样地，对于本来是 1 的点 ( 2 )，它是没有影响的。
综上，建图方法如下：省略反向边（价值为 $0$ ）；
1.对于01点：
若为 0，则连 $(S,x,v_x)$；
若为 1，则连 $(x,T,v_x)$；
2.对于要求：
若要求 0，则建虚点 $x$ 连 $(S,x,w_i)$，并将要求的点 $y$ 连 $(x,y,inf)$；
若要求 1，则建虚点 $x$ 连 $(x,T,w_i)$，并将要求的点 $y$ 连 $(y,x,inf)$；
建完图跑最小割即可。
------
#### [P4313 文理分科](https://www.luogu.com.cn/problem/P4313)
上道题每个点初始就分好类了，自然要放到两边去建图。
这道题一个人初始没有规定类别，那容易想到直接 $(S,x,a_{x}),(x,T,b_x)$ 让他割掉一个不选。
然后“旁边的都相同”这个跟上题一样，就是**给一些点，如果都选了...则有贡献**，还是转化为割边的语言来刻画问题：
- **条件或**：将两条边 $a,b$ 串联成路径，表示要么割 $a$，要么割 $b$。
- **条件与**：将两条边 $a,b$ 并联到一个虚点上，表示 $a,b$ 必须都割掉才能使路径不连通。
这道题的条件关系就是：
（旁边的人选 b AND 自己选 b）$\iff$（得到 same_b 的贡献）我们改一下变成：
（得到 same_b 的贡献）则一定（旁边的人选 b AND 自己选 b）。注意不要搞反了，感受一下肯定是**保证你贡献一定不会算多只会算少**，然后你是个最优化算法，所以你取到上界不多不少。
使用 2-SAT 的转化，$a\implies b$ 等价于 $\neg a\vee b$。即 $a\implies b$ 为假当且仅当 $a$ 为真、$b$ 为假。
（放弃 same_b 的贡献）OR（旁边的人都选 b AND 自己选 b）。
（割掉 same_b 的边）OR（旁边的人都割 a AND 自己割 a）。
好了可以建图了，（旁边的人都割 a AND 自己割 a）就把限制的几个人都连向虚点 $u$，再 $u\to T$ 表示或条件。
实际上也不太需要如此严谨的逻辑推导，**感受一下**即可：
- 要么放弃 same_b 的贡献，要么你保留 same_b 的贡献就必须割掉所有相关 a 的边。
----------
### （2）费用流刻画
给你一些选点的限制，求选的点的最值。
可以使用**连边和流量表示限制**，**费用表示选点的贡献**；跑费用流；
以下几个例子，使用了流量，最大流等来表示限制，而使用路径经过的费用来计算贡献。
- 在 graph 一题中，要求“只走 $k$ 条路径，最大化经过点数”：
可以设置初始总流量为 $k$，让路径去经过点，用经过的费用来统计选点的个数。每个点只走一次的限制：可以拆出入点中间流量为 $1$。
- 在通信一题中，要求“每个点都满足两个条件之一”：
可以用 $n$ 条初始流，选择条件（路径）最终都到达 $T$（最大流 $n$）来刻画。
- 在志愿者招募一题中，要求“每天至少被覆盖 $a_i$ 次”：
可以转化为 $\min(t_i-a_i)\ge 0$，用流量来刻画 $\min$ 将所有点串联在一起，流一下就取得了 $\min$。
一条边的总流量可以并联拆分成多条边流量的和，每个人的贡献就可以描述为跨过一个区间的路径。
----
#### [Gmoj7892.谷拉符(graph)](https://gmoj.net/senior/#main/show/7892)：路径覆盖点数最大值。
题面
$n$ 个点，每个点有 $a_i$；满足以下任意一条条件的 $i,j(i<j)$ 有连边：
- $|a_i-a_j|=A$；
- $a_i=a_j\times B$ 或 $a_j=a_i\times B$；
- $a_i\equiv a_j(mod\ C)$；
选出 $k$ 条路径，满足它们互不相交，求路径覆盖的点数量的最大值；$n,k\le 3000$；
题解
考虑用最大费用最大流；默认边的参数顺序为：$(flow,cost)$ ；
1.**用费用表示选点**
经过一个点即选点，但是网络流中点一般不具有点权，一般靠边；所以我们把点 $x$ 拆开为入点 $in[x]$ 和出点 $out[x]$。
中间连一条费用为 $1$ 的边，这样从 $in[x]$ 走到 $out[x]$ 就能得到 $1$ 的费用贡献；
2.**用连边和流量表示限制**
- $ k $ 条路径，且互不相交：
即每个点只能经过一次，可以想到 $in[x]$ 到 $out[x]$ 的流量为 $1$；
$k$ 条路径比较抽象，可以画个图看看；
发现可以建一个 $ss$ 点，将 $S$ 到 $ss$ 连一条 $(k,0)$ 的边，再把 $ss$ 与 $in[x]$ 连一条 $(1,0)$ 的边；
最后，把 $out[x]$ 与 $T$ 连一条 $(inf,0)$ 的边
- 对 $i<j$，满足…条件：
想到可以 $O(n^2)$ 枚举 $i,j$，若满足，将对应的 $out[i]$ 和 $in[j]$ 连 $(1,0)$ 的边，
这样有路径 $in[i]\rightarrow^ {1,1} out[i] \rightarrow^{1,0} in[j] \rightarrow^{1,1} out[j]$能造成 $2$ 的贡献，符合题意；
但是这样的边数是 $O(n^2)$ 的；为什么呢？
对于 $A,B$ 条件可以构造很多相同的数字，发现有很多冗余的边，不可能成为答案；
考虑把相同的数字按照下标顺序，依次连接；然后每次只连满足条件、且下标最小的；
对于 $A,B$ 都要分两种情况（绝对值）；
对于 $C$ 条件本身就具有传递性，也是 $O(n^2)$ 的；
同样可以把同余的数依次相连；这样边数就变成了 $O(n)$；
跑一边最大费用最大流即可；
-----------
#### [P5331 [SNOI2019] 通信](https://www.luogu.com.cn/problem/P5331)：cdq 分治优化建图。
题面
$n$ 个排成一列的哨站要进行通信。第 $i$ 个哨站的频段为 $a_i$。
每个哨站 $i$ 需要选择以下二者之一：
1. 直接连接到控制中心，代价为 $W$；
2. 连接到前面的某个哨站 $j$ ($j<i$)，代价为 $|a_i-a_j|$。
每个哨站只能被后面的至多一个哨站连接。
请你求出最小可能的代价和。
对于所有数据，$1 \leq n \leq 1000$，$0 \leq W,a_i \leq 10^9$。
题解
CDQ分治优化费用流好题；
这种最优化代价题，且数据范围小的，可以考虑网络流；
先暴力费用流：
考虑对一个点拆成“入点”和“出点”；
选择1：$(in[x],T,0, W)$；
选择2：$(in[i],out[j],1,|a[i]-a[j]|)$；
但是 $O(n^2)$ 的边数不行；
发现这种 $O(n^2)$ 的经常可以用一条**“交换链”**优化（与上一题相同）；
但是我们发现本题还有 $j<i$；
处理偏序问题，那当然要 CDQ 分治！
每次对左区间建虚点，然后右区间连向左区间即可；
虚点是防止干扰；
细节很多，需要弄清楚**整个图的结构**，还要考虑**流量是否为 $inf$**；
------------
#### [P3980 [NOI2008] 志愿者招募](https://www.luogu.com.cn/problem/P3980)：刻画 $\min$ 和流量拆分。
大部分题解只讲解了本题的建图方式并给出解释，少有题解真正讲明白这种看似奇妙建图的来源。
本题解将尝试不通过线性规划的方式，使用网络流语言讲明白本题的建图推导过程，并给出其背后的逻辑。
> 如果我们不满足于认识现有的结果，就要发掘出问题背后的脉络，
> 认识到看起来“神机妙算”的证明，拆掉之前的**脚手架**长什么样。
>
> > Carl Friedrich Gauss: “凡是有自尊心的建筑师，在瑰丽的大厦建成之后，决不会把脚手架留在那里。”
下文简记一条 $x\to y$ 流量为 $f$，费用为 $c$ 的边为 $(x,y,f,c)$。下文所有 $\infty $ 指一个足够大的整数，取其为 $10^{18}$。
令第 $i$ 天被覆盖了 $t_i$ 次，题目限制即 $\forall i,t_i\ge a_i$，等价于 $\min(t_i-a_i)\ge 0$。
使用**流量取 $\min$ 的特性刻画 $\min(t_i-a_i)$**，那么将所有天对应的边串在一起即可描述。具体地，令第 $i$ 天对应点 $i$，$i\to i+1$ 的流量为 $t_i-a_i$，$S\to a_1,a_{n+1}\to T$。那么我们要求最大流 $\ge 0$。
考察选择一个人 $(l_i,r_i,c_i)$ 对流量的贡献。不妨考虑一种简单情况：$l_i=r_i=j$。
由于**一条边的流量可以拆分为并联的多条边的流量之和**，我们可以将原来流量为 $t_i-a_i$ 拆为一条 $-a_i$ 的边和一条 $t_i$ 的边，其中 $t_i$ 在 $l_i=r_i$ 的情况下就是我们选了多少次这个人。
我们自然想到额外连一条 $j\to j+1$ 流量为 $\infty$，费用为 $c_i$ 的边。这样取一个人这条边流量 $+1$，并造成 $c_i$ 的贡献。
实际上这是可以**推广**的。对于一个人 $(l_i,r_i,c_i)$，它会贡献点 $[l_i,r_i]$ 的边的流量。由于将之前所述两条相邻 $(j,j+1,\infty,c_i)$ 的边**合并**为一条 $(j,j+2,\infty,c_i)$ 是等价的，我们可以想到连一条 $(l_i,r_i+1,\infty,c_i)$ 的边。注意这里要覆盖 $[l_i,r_i]$ 对应的所有边，包括 $r_i\to r_i+1$ 的边。
由于我们不能连流量为 $-a_i$ 的边，可以将其整体 $+\infty$，即连流量为 $\infty -a_i$ 的边，要求最大流 $\ge \infty$。
我们只需要在汇点处限制最大流 $\le \infty$，即 $n+1\to T$ 流量为 $\infty$，那么费用流算法就会在保证最大流取到 $\infty $ 的情况下，使总费用尽量小，这是符合我们的要求的。
总结来看，建图：对于每天 $(i,i+1,\infty-a_i,0)$，对于每个人 $(l_i,r_i+1,\infty ,c_i)$，源汇点连边 $(S,1,\infty,0),(n+1,T,\infty ,0)$。使用费用流算法即可解决。
由此，我们看到了，本题中两个反常的建图方式的来源：
- 链式建图：为了刻画 $\min(t_i-a_i)$，将边串在一起。
- 一个人连一条跨过区间的边：实际上利用了流量的可拆分性和可合并性进行转化。
即一条边的流量可以拆分为并联的多条边的流量之和；
连一条跨过一段区间的、流量为 $x$ 的边等价于将区间内的所有边流量加上 $x$。
## 杂题
#### Gmoj8284. 选课
要求：一次操作：每行取一个；每列最多取一个；$(i,j)$ 最多取 $a_{i,j}$ 次；问最多操作几次；
把取的操作变为“流过”；行 $x$，列 $y$；
那么，$x$ 必须全部流到，$y$ 最多流一次；
显然把 $x$ 放在 $T$ 侧，$y$ 放在 $S$ 侧，这样能满足条件；
即最大流流满 $x$，$(S,y)$ 容量为 $1$；
可能会担心多次操作下，一次操作的流与另一个操作的流对换了，但是这是可以换回来的，是等价的；
----------
#### [P1402 酒店之王](https://www.luogu.com.cn/problem/P1402)：最大流 3-最大匹配。
一个人必须匹配到合适的房间和菜才能造成 $1$ 的贡献，不难想到直接用最大流的路径刻画。
如果一个人 $x$ 能和房间 $y$ 匹配，那么连 $y\to x$，如果一个人能和菜 $z$ 匹配，那么连 $x\to z$。一条路径，必须经过了 $y\to x\to z$ 才是一条增广路。这样最大流就是最大匹配。
由于一个人只能匹配一次，拆点中间流量为 $1$ 即可。
---------
#### [[ARC107F] Sum of Abs](https://www.luogu.com.cn/problem/AT_arc107_f)：正负贡献转最小割。
这道题的数据范围很像网络流，但是我们不知道如何用网络流统计和的贡献。
但是可以利用网络流的思路：**制造矛盾选择，用最小割模型**。
那么我们观察贡献形式，我们发现如果正权点和负权点连通，那么**要不删掉其一、要不减去正负抵消的贡献**。
连通是好说的，首先把点拆点，然后正连 $S$，负连 $T$，就能制造出路径。
但是正负抵消的贡献很难说，因为我们不知道连通块是正的还是负的。
其实 $|\sum a|=\sum |a|-2 \min(\sum_{a\ge 0} |a|,\sum_{a<0}|a|)$，所以我们可以通过在 $(S,+),(-,T)$ 的流量来实现 $min$ 的操作
这样就成功转化了。
思考过程中曾经提出“正负只能留一个”但是这样是不对的，因为忽略了正负抵消的贡献。
-------------
#### [P1935 [国家集训队] 圈地计划](https://www.luogu.com.cn/problem/P1935)：二分图染色转化。
有时转化不在建图上。
我们发现它的限制很恶心，是“选择不同，造成贡献”，这样使得我们无法在建图中构建出并联。
那么能不能在建图外做转化呢？可以，由于连边是二分图，所以我们可以**二分图染色**后对黑点，**调换**它的两种选择。这样就转化为了“选择相同，造成贡献”。
即相邻 $4$ 个点，分别如果与中间相同，就造成贡献，经典的最小割。
--------------
#### [ABC397G] Maximize Distance：拆路径贡献 + 多层建图。
考虑判断 $ans=1$ 时，答案即最小割。考虑扩展。
当 $ans=2$ 时，我们要求每条路径都有至少两条边被割，可以考虑“割一次后转到另一个图”，这样能够实现割两次。
当然我们不需要拘泥于最小割的经典选择套路，因为那样构造不出来。
考虑我们现在割了一条边，于是我们连一条边到一个新图上，而原图依然保留，
那么就相当于在两个图上分别统计了贡献，所以是可行的。
-----------
#### [P1791 [国家集训队] 人员雇佣 ](https://www.luogu.com.cn/problem/P1791)：最小割 + 转化。
高手建图。
考虑最小割，首先每个人一个点向 S,T 各连边，分别表示“不选”的代价，“选”的代价。
刻画点对选择方案对应的贡献，对于无序对 $(i,j)$：
- $i,j$ 都选：$-a_i-a_j+2E_{i,j}$。
- $i,j$ 都不选：$0$。
- $i$ 选 $j$ 不选：$-a_i-E{i,j}$。
直接上最小割过于生硬，进行一些转化：
构造不选的代价，全部减 $-2E_{i,j}$，注意是无序对，总和 $+\sum \sum E_{i,j}$。
注意到如果 $j$ 不选，对不选的 $i$ 贡献为 $E_{i,j}$，对选的 $i$ 贡献 $3E_{i,j}$，于是可以构造不选的代价为 $\sum_{i} E_{i,j}$。
然后在 $i,j$ 之间连边 $2E_{i,j}$ 即可完成对选的贡献。
-----------
#### [2025.8.9 A组 T3 我图呢(graph)](https://gmoj.net/senior/#contest/show/4439/2)：$\infty$ 加权最小割 + 方案。
求二分图的最大独立集的最大权，即**保证点数最大后使权值最大**。
考虑费用流，但是难以建图。由于是“最大费用最大流”，实际上可以将“点数”的价值 $+\infty$，然后和权值加在一起。
那么就转化为普通的最小割模型了，即求二分图最大权独立集。
由于是二分图，可以染色后，$col=0$ 的连 $S$，$col=1$ 的连 $T$，流量为各自的权值。
方案呢？
考虑网络流结束后，从 $S$ 走流量 $>0$ 的边，能到达的点。
$col=0$ 中，那些直接能被走到的点肯定是被选择的（没有被割掉），
但是注意到还有些点虽然没有被割掉，但是在增广路中被割掉的边一起减成了 $0$，实际上，这种点可以被增广路中的反向边遍历到。
然后考虑 $col=1$ 的点，如果被遍历到了，那么就没有被选择。
所以如果 $col[i]\not= vis[i]$，$i$ 就在选择方案中。
------------