网络流与二分图
UnionRE
·
·
算法·理论
2025/4/6：添加了题目。重新提交。
如果你想查看卡常方法：请转到章节：几个玄学优化。
题单
网络流
EK
首先我们会想到一个暴力：暴力枚举每一条路径，然后流一遍，于是……
这样是错误的。
我们很可能有沿着蓝色的路径流：
这样流了之后，就没法继续流了。因此我们需要反悔。
建立原图 G 的残留网络 G'，我们规定 G,G' 上的对应边的边权之和相加等于边的容量。
于是我们可以愉快地流绿色的边了 qwq。
这其实相当于流了 1\to2\to4,1\to3\to4 两条路径。
这就是 EK 的核心思想。O(VE^2)。
Dinic
我们考虑多路增广。
我们先进行一次 bfs，将图分为很多层。
我们改用 dfs 进行增广。
第一条增广路：
第二条增广路（此时 1\to2 的流量只剩下 10-8=2 了）。完成后回溯，并更新残留网络。
更新残留网络。
第三条增广路：
再次分层。
如此往复。
当前弧优化 dinic
:::info[为什么能优化]
看下面的图：
上面的 3 条路径中，除了 \to 7 的路径之外，都跑满了（有一个流量为 1 的限制）
那我们再到这里的时候：
我们选择优化，不找上面两条了。
:::
代码就不贴了，改成 for(int i=cur[u];i&∩i=ed[i].nxt) 并更新 cur[u]=i; 就行了。
最大流最小割
不会证明，感性理解。
:::warning[理解]{open}
直观理解：
假设最大流为 f，找一个割集，把网络分割成了两个部分，那现在最大流就是 0 了，相当于找的割集得把原来的流阻断。
割要最小，就要恰好阻断所有流。如果割 <f，说明一定存在一条 S\to T 的路径有流，此时没有把网络分成两个部分。所以割一定 \ge f ,如果 >f 了，说明割集把最大流 f 阻断了，然而有多余流量的边，把多余流量的边去了，就是最小割 f 了。
:::
例题
P3931 SAC E#1 - 一道难题 Tree
我们显然可以看做最小割。
对于原来的树 T，新建超级汇点 t 连接所有叶子结点，对每一条父亲到儿子的边建立边，构成 G，跑最小割。
:::info[code]
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1000002,inf=INT_MAX;
struct edge{
int u,v,w,nxt;
}ed[maxn];
struct edge2{
int v,w;
};
int n,s,t,lvl[maxn],head[maxn],cur[maxn],tot=2;
vector<edge2> G[maxn];
void adde(int u,int v,int w){
ed[tot]={u,v,w,head[u]};
head[u]=tot;
tot++;
}
void Dfs(int u,int fa){
bool leaf=1;
for(auto [v,w]:G[u]){
if(v!=fa){
Dfs(v,u);
adde(u,v,w);
adde(v,u,0);
leaf=0;
}
}
if(leaf){
adde(u,t,inf);
adde(t,u,0);
}
}
bool bfs(){
queue<int> q;
q.push(s);
memset(lvl,-1,sizeof(lvl));
lvl[s]=0;
while(q.size()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=ed[i].nxt){
int v=ed[i].v,w=ed[i].w;
if(w&&lvl[v]==-1){
lvl[v]=lvl[u]+1;
q.push(v);
if(v==t)return 1;
}
}
}
return 0;
}
int dfs(int u,int cap){
int flow=0;
if(u==t)return cap;
for(int i=cur[u];i&∩i=ed[i].nxt){
cur[u]=i;//u往下这一路已经处理完了，不用再次遍历
int v=ed[i].v,w=ed[i].w;
if(w&&lvl[v]==lvl[u]+1){
int use=dfs(v,min(cap,w));
if(use==0)lvl[v]=-1;
if(use>0){
ed[i].w-=use;
ed[i^1].w+=use;
cap-=use;
flow+=use;
}
}
}
return flow;
}
void dinic(){
int ans=0;
while(bfs()){
memcpy(cur,head,sizeof(head));
ans+=dfs(s,inf);
}
cout<<ans;
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);
cin>>n>>s;
t=n+1;//超汇
for(int i=1;i<n;i++){
int u,v,w;
cin>>u>>v>>w;
G[u].push_back({v,w});
G[v].push_back({u,w});
}
Dfs(s,0);
dinic();
return 0;
}
:::
P3254 圆桌问题
考虑将造一个超级源点，连接每一个单位，容量为这个单位的人数，并造一个超级汇点，连接每一个餐桌，容量为餐桌能坐的人数。
对于单位和餐桌，连接一条容量为 1 的边，表示同一单位的代表中，只有一个能坐在这个餐桌。（两两餐桌不同）
最后跑网络流。对于方案，我们直接看单位到餐桌的边是否流满了（剩余流量为 0）就可以了。
给一个样例的图片：
:::info[code]
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=275,M=5005,inf=2147483647;
int n,m,s,t;
int lvl[N];//层数
struct edge{
int u,v,w;
int nxt;
}ed[M*2];
int head[N],cur[N],cnt=2;
void adde(int u,int v,int w){
ed[cnt].u=u;
ed[cnt].v=v;
ed[cnt].w=w;
ed[cnt].nxt=head[u];
head[u]=cnt;
cnt++;
}
bool bfs(){
queue<int> q;
for(int i=1;i<=n+m+2;i++)lvl[i]=-1;
lvl[s]=0;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=ed[i].nxt){
if(lvl[ed[i].v]==-1&&ed[i].w>0){
lvl[ed[i].v]=lvl[u]+1;
q.push(ed[i].v);
if(ed[i].v==t)return 1;
}
}
}
return(lvl[t]!=-1);
}
int dfs(int u,int cap){//cap:容量
int flow=0;//跑过的流
if(u==t)return cap;
for(int i=cur[u];i&∩i=ed[i].nxt){
cur[u]=i;
int v=ed[i].v,w=ed[i].w;
if(w&&lvl[v]==lvl[u]+1){
int use=dfs(v,min(cap,w));
if(use==0)lvl[v]=-1;
if(use>0){
ed[i].w-=use;
ed[i^1].w+=use;
cap-=use;
flow+=use;
}
}
}
return flow;
}
int dinic(){
int ans=0;
while(bfs()){
memcpy(cur,head,sizeof(head));
ans+=dfs(s,inf);
}
return ans;
}
int ren=0;
vector<int> table[N];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>m>>n;
s=1;t=n+m+2;
for(int i=1;i<=m;i++){
int ri;
cin>>ri;
ren+=ri;
adde(s,i+1,ri);
adde(i+1,s,0);
}
for(int i=1;i<=n;i++){
int ci;
cin>>ci;
adde(i+m+1,t,ci);
adde(t,i+m+1,0);
}
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
adde(i+1,j+m+1,1);
adde(j+m+1,i+1,0);
}
}
if(dinic()<ren){
cout<<0;
return 0;
}
cout<<1<<endl;
for(int i=2;i<=m+1;i++){//man
for(int j=head[i];j;j=ed[j].nxt){
if(!ed[j].w)cout<<ed[j].v-m-1<<' ';
}
cout<<endl;
}
return 0;
}
:::
费用流
无负圈的费用流
我们在选择增广路的时候，尽量要选择距离小的路径进行增流，直到无法增加再切换到另一条。
具体的，我们需要先进行最短路，预处理 s 到每一个点 u 的距离 dis_u。
bool spfa(){
for(int i=0;i<maxn;i++)dis[i]=inf;
dis[s]=0;
inq[s]=1;
q.push(s);
while(q.size()){
int u=q.front();
q.pop();
inq[u]=0;
for(int i=head[u];i;i=ed[i].nxt){
int v=ed[i].v,c=ed[i].c,flow=ed[i].w;
if(dis[v]>dis[u]+c&&flow){//这里要判断能不能过
dis[v]=dis[u]+c;
if(!inq[v])q.push(v);
inq[v]=1;
}
}
}
return dis[t]!=inf;
}
同时，我们要在 dfs 函数上进行改进：选择最短的那条路径。
int dfs(int u,int cap){
int flow=0;
if(u==t)return cap;
vis[u]=1;
for(int i=cur[u];i&∩i=ed[i].nxt){
cur[u]=i;
int v=ed[i].v,c=ed[i].c,fl=ed[i].w;
if(dis[v]==dis[u]+c&&fl&&!vis[v]){//判断最短的条件就是 dis[v]=dis[u]+w（松弛到不能松弛）
int use=dfs(v,min(cap,fl));
if(use>0){
ed[i].w-=use;
ed[i^1].w+=use;
flow+=use;
cap-=use;
}
}
}
vis[u]=0;
return flow;
}
有同学要问了：vis 数组是干嘛的？
原因：可能存在单位权值为 0 的环，所以在 dfs 找增广路时，需要对访问当前这条增广路的点进行标记，避免死循环。
最后是统计答案：
pair<int,int> dinic(){
int flow=0,cost=0;
while(spfa()){
memcpy(cur,head,sizeof(head));
int fl=dfs(s,inf);
flow+=fl;
cost+=fl*dis[t];
}
return {flow,cost};
}
有的同学又要问了：你这个 C(G)=\sum\limits_{<u,v>\in E}c_{u\to v}\cdot flow_{u\to v}，但是你怎么能直接把这一轮的 fl 和 dis[t] 相乘呢。
原因：你刚刚不是走的是最短的路径吗。
那么对于两条路径 P_1,P_2：
那么答案：\Delta cost=flow(P_1)\sum\limits_{e\in P_1} c_e+flow(P_2)\sum\limits_{e\in P_2}c_e=\sum c\cdot[flow(P_1)+flow(P_2)]
同理，对于多条最短路径，\Delta cost=\sum c\cdot\sum flow(Path)
完整代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=500100,inf=INT_MAX;
int n,m,s,t,head[maxn],tot=2,dis[maxn],cur[maxn];//inqueue
struct edge{
int u,v,w,c,nxt;
}ed[maxn];
bool inq[maxn],vis[maxn];
queue<int> q;
void adde(int u,int v,int w,int c){
ed[tot]={u,v,w,c,head[u]};
head[u]=tot;
tot++;
}
bool spfa(){
for(int i=0;i<maxn;i++)dis[i]=inf;
dis[s]=0;
inq[s]=1;
q.push(s);
while(q.size()){
int u=q.front();
q.pop();
inq[u]=0;
for(int i=head[u];i;i=ed[i].nxt){
int v=ed[i].v,c=ed[i].c,flow=ed[i].w;
if(dis[v]>dis[u]+c&&flow){
dis[v]=dis[u]+c;
if(!inq[v])q.push(v);
inq[v]=1;
}
}
}
return dis[t]!=inf;
}
int dfs(int u,int cap){
int flow=0;
if(u==t)return cap;
vis[u]=1;
for(int i=cur[u];i&∩i=ed[i].nxt){
cur[u]=i;
int v=ed[i].v,c=ed[i].c,fl=ed[i].w;
if(dis[v]==dis[u]+c&&fl&&!vis[v]){
int use=dfs(v,min(cap,fl));
if(use>0){
ed[i].w-=use;
ed[i^1].w+=use;
flow+=use;
cap-=use;
}
}
}
vis[u]=0;
return flow;
}
pair<int,int> dinic(){
int flow=0,cost=0;
while(spfa()){
memcpy(cur,head,sizeof(head));
int fl=dfs(s,inf);
flow+=fl;
cost+=fl*dis[t];
}
return {flow,cost};
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++){
int u,v,w,c;
cin>>u>>v>>w>>c;
adde(u,v,w,c);
adde(v,u,0,-c);
}
pair<int,int> ans=dinic();
cout<<ans.first<<' '<<ans.second;
return 0;
}
例题
P4014 分配问题
简洁明了，超源超汇。
将 s 与人建边 \{1,0\}，将 t 与工作建边 \{1,0\}，将人与工作建边 \{1,c_{i,j}\}。
注意跑一次最小费用流，一次最大费用流。
:::info[code]
#include<bits/stdc++.h>
using namespace std;
const int maxn=5510,inf=INT_MAX;
int n,m,s,t,head[maxn],tot=2,dis[maxn],cur[maxn];//inqueue
struct edge{
int u,v,w,c,nxt;
}ed[maxn],ed2[maxn];
bool inq[maxn],vis[maxn];
int c[51][51];
queue<int> q;
void adde(int u,int v,int w,int c){
ed[tot]={u,v,w,c,head[u]};
head[u]=tot;
tot++;
}
bool spfa(){
for(int i=0;i<maxn;i++)dis[i]=inf;
dis[s]=0;
inq[s]=1;
q.push(s);
while(q.size()){
int u=q.front();
q.pop();
inq[u]=0;
for(int i=head[u];i;i=ed[i].nxt){
int v=ed[i].v,c=ed[i].c,flow=ed[i].w;
if(dis[v]>dis[u]+c&&flow){
dis[v]=dis[u]+c;
if(!inq[v])q.push(v);
inq[v]=1;
}
}
}
return dis[t]!=inf;
}
bool spfa2(){
for(int i=0;i<maxn;i++)dis[i]=-inf;
dis[s]=0;
inq[s]=1;
q.push(s);
while(q.size()){
int u=q.front();
q.pop();
inq[u]=0;
for(int i=head[u];i;i=ed[i].nxt){
int v=ed[i].v,c=ed[i].c,flow=ed[i].w;
if(dis[v]<dis[u]+c&&flow){
dis[v]=dis[u]+c;
if(!inq[v])q.push(v);
inq[v]=1;
}
}
}
return dis[t]!=-inf;
}
int dfs(int u,int cap){
int flow=0;
if(u==t)return cap;
vis[u]=1;
for(int i=cur[u];i&∩i=ed[i].nxt){
cur[u]=i;
int v=ed[i].v,c=ed[i].c,fl=ed[i].w;
if(dis[v]==dis[u]+c&&fl&&!vis[v]){
int use=dfs(v,min(cap,fl));
if(use>0){
ed[i].w-=use;
ed[i^1].w+=use;
flow+=use;
cap-=use;
}
}
}
vis[u]=0;
return flow;
}
pair<int,int> dinic(){
int flow=0,cost=0;
while(spfa()){
memcpy(cur,head,sizeof(head));
int fl=dfs(s,inf);
flow+=fl;
cost+=fl*dis[t];
}
return {flow,cost};
}
pair<int,int> dinic2(){
int flow=0,cost=0;
while(spfa2()){
memcpy(cur,head,sizeof(head));
int fl=dfs(s,inf);
flow+=fl;
cost+=fl*dis[t];
}
return {flow,cost};
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>c[i][j];
}
}
s=0,t=2*n+1;
for(int i=1;i<=n;i++){
adde(s,i,1,0);
adde(i,s,0,0);
}
for(int i=1;i<=n;i++){
adde(i+n,t,1,0);
adde(t,i+n,0,0);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
adde(i,j+n,1,c[i][j]);
adde(j+n,i,0,-c[i][j]);
}
}
for(int i=2;i<=tot;i++)ed2[i]=ed[i];
cout<<dinic().second<<endl;
for(int i=2;i<=tot;i++)ed[i]=ed2[i];
cout<<dinic2().second;
return 0;
}
:::
P4015 运输问题
和上面那道题一样，多了个数量而已 qwq，于是 s 到仓库，t 到商店的容量就不是 1，是 a_i,b_j 了喵。
:::info[code]
#include<bits/stdc++.h>
using namespace std;
const int maxn=40101,inf=INT_MAX;
int n,m,s,t,head[maxn],tot=2,dis[maxn],cur[maxn];//inqueue
struct edge{
int u,v,w,c,nxt;
}ed[maxn],ed2[maxn];
bool inq[maxn],vis[maxn];
int c[151][151],a[101],b[101];
queue<int> q;
void adde(int u,int v,int w,int c){
ed[tot]={u,v,w,c,head[u]};
head[u]=tot;
tot++;
}
bool spfa(){
for(int i=0;i<maxn;i++)dis[i]=inf;
dis[s]=0;
inq[s]=1;
q.push(s);
while(q.size()){
int u=q.front();
q.pop();
inq[u]=0;
for(int i=head[u];i;i=ed[i].nxt){
int v=ed[i].v,c=ed[i].c,flow=ed[i].w;
if(dis[v]>dis[u]+c&&flow){
dis[v]=dis[u]+c;
if(!inq[v])q.push(v);
inq[v]=1;
}
}
}
return dis[t]!=inf;
}
bool spfa2(){
for(int i=0;i<maxn;i++)dis[i]=-inf;
dis[s]=0;
inq[s]=1;
q.push(s);
while(q.size()){
int u=q.front();
q.pop();
inq[u]=0;
for(int i=head[u];i;i=ed[i].nxt){
int v=ed[i].v,c=ed[i].c,flow=ed[i].w;
if(dis[v]<dis[u]+c&&flow){
dis[v]=dis[u]+c;
if(!inq[v])q.push(v);
inq[v]=1;
}
}
}
return dis[t]!=-inf;
}
int dfs(int u,int cap){
int flow=0;
if(u==t)return cap;
vis[u]=1;
for(int i=cur[u];i&∩i=ed[i].nxt){
cur[u]=i;
int v=ed[i].v,c=ed[i].c,fl=ed[i].w;
if(dis[v]==dis[u]+c&&fl&&!vis[v]){
int use=dfs(v,min(cap,fl));
if(use>0){
ed[i].w-=use;
ed[i^1].w+=use;
flow+=use;
cap-=use;
}
}
}
vis[u]=0;
return flow;
}
pair<int,int> dinic(){
int flow=0,cost=0;
while(spfa()){
memcpy(cur,head,sizeof(head));
int fl=dfs(s,inf);
flow+=fl;
cost+=fl*dis[t];
}
return {flow,cost};
}
pair<int,int> dinic2(){
int flow=0,cost=0;
while(spfa2()){
memcpy(cur,head,sizeof(head));
int fl=dfs(s,inf);
flow+=fl;
cost+=fl*dis[t];
}
return {flow,cost};
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);
cin>>m>>n;
for(int i=1;i<=m;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
cin>>c[i][j];
}
}
s=0,t=m+n+1;
for(int i=1;i<=m;i++){
adde(s,i,a[i],0);
adde(i,s,0,0);
}
for(int i=1;i<=n;i++){
adde(i+m,t,b[i],0);
adde(t,i+m,0,0);
}
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
adde(i,j+m,inf,c[i][j]);
adde(j+m,i,0,-c[i][j]);
}
}
for(int i=2;i<=tot;i++)ed2[i]=ed[i];
cout<<dinic().second<<endl;
for(int i=2;i<=tot;i++)ed[i]=ed2[i];
cout<<dinic2().second;
return 0;
}
:::
农场之旅—POJ2135
:::info[题目描述]
题目描述：
约翰的农场有 N(1\le N\le 1000) 块田地，编号为1到N。第1块田地上有他的房子，第N块田地上有一个大谷仓。有 M(1\le M\le10000) 条道路连接田地，每条道路都连接了两个不同的田地，并且长度大于 0 小于 35000。他从家开始，可能穿过一些田地，最后到谷仓。后来，他又回到家里。
他希望自己的旅程尽可能短，但不想经过任何一条道路超过一次。
:::
我们考虑利用网络流的性质。两点之间建立边，流量为 1，费用为 w，这样就可以来做到每条边经过一次的性质了。
建立超级源点 S，超级汇点 T，S 与 1 连边 \{2,0\}，n 与 T 连边 \{2,0\}，这样能保证来往共两次。
注意到 1\to n 的路径和 n\to 1 的路径互为反向，且 \sum\limits_{e\in Path(1\to n)} w_e=\sum\limits_{e\in Path(n\to 1)} w_e，边权和相等。所以我们其实只需要跑一遍费用流，就可以计算了。
P2770 航空路线问题
和上面的那道题很像啊。
我们考虑拆点，把 u 拆成入点 u 和出点 u'，建立边 e_{u\to u'}，费用为 1，容量为 1。
最后跑一遍最大费用最大流即可。
特殊处理 u\to v 的边，这条边的容量为 2。
判断无解嘛，就是判断 t' 的流量是否为 2。注：t'=2n。
:::info[code]
#include<bits/stdc++.h>
using namespace std;
const int maxn=10001,inf=INT_MAX;
string name[maxn];
struct edge{
int u,v,w,c,nxt;
}ed[maxn];
int tot=2,s,t,dis[maxn],head[maxn],cur[maxn],n;
bool inq[maxn],vis[maxn];
void adde(int u,int v,int w,int c){
ed[tot]={u,v,w,c,head[u]};
head[u]=tot;
tot++;
}
bool spfa(){
queue<int> q;
for(int i=0;i<maxn;i++)dis[i]=inf;
dis[s]=0;
q.push(s);
inq[s]=1;
while(q.size()){
int u=q.front();
q.pop();
inq[u]=0;
for(int i=head[u];i;i=ed[i].nxt){
int v=ed[i].v,flow=ed[i].w,c=ed[i].c;
if(dis[v]>dis[u]+c&&flow){
dis[v]=dis[u]+c;
if(!inq[v])q.push(v);
inq[v]=1;
}
}
}
return dis[t]!=inf;
}
int dfs(int u,int cap){
int flow=0;
vis[u]=1;
if(u==t)return cap;
for(int i=cur[u];i&∩i=ed[i].nxt){
cur[u]=i;
int v=ed[i].v,fl=ed[i].w,c=ed[i].c;
if(dis[v]==dis[u]+c&&fl&&!vis[v]){
int use=dfs(v,min(cap,fl));
if(use>0){
cap-=use;
flow+=use;
ed[i].w-=use;
ed[i^1].w+=use;
}
}
}
vis[u]=0;
return flow;
}
pair<int,int> dinic(){
int flow=0,cost=0;
while(spfa()){
memset(vis,0,sizeof(vis));
memcpy(cur,head,sizeof(head));
int fl=dfs(s,inf);
flow+=fl;
cost+=fl*dis[t];
}
return {flow,cost};
}
map<string,int> re;
vector<int> rt1,rt2;
bool route[maxn];
void dfs1(int u){
if(u!=n+1)route[u]=1;
if(u==t)return;
if(u<=n)rt1.push_back(u);
for(int i=head[u];i;i=ed[i].nxt){
int v=ed[i].v,fl=ed[i].w,c=ed[i].c;
if(c<=0&&fl==0){
dfs1(v);
break;
}
}
}
void dfs2(int u){
if(u<=n)rt2.push_back(u);
for(int i=head[u];i;i=ed[i].nxt){
int v=ed[i].v,fl=ed[i].w,c=ed[i].c;
if(c<=0&&fl==0&&!route[v]){
dfs2(v);
break;
}
}
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);
int m;
cin>>n>>m;
s=1,t=n*2;
for(int i=1;i<=n;i++){
cin>>name[i];
re[name[i]]=i;
}
adde(1,1+n,2,0);
adde(1+n,1,0,0);
adde(n,n*2,2,0);
adde(n*2,n,0,0);
for(int i=2;i<n;i++){
adde(i,i+n,1,0);
adde(i+n,i,0,0);
}
for(int i=1;i<=m;i++){
string su,sv;
cin>>su>>sv;
int u=re[su],v=re[sv];
if(u>v)swap(u,v);
adde(u+n,v,1+(u==1&&v==n),-1);
adde(v,u+n,0,1);
}
pair<int,int> ans=dinic();
if(ans.first!=2){
cout<<"No Solution!";
return 0;
}
cout<<-ans.second<<endl;
dfs1(s);
for(auto i:rt1){
cout<<name[i]<<endl;
}
dfs2(1+n);
reverse(rt2.begin(),rt2.end());
for(auto i:rt2){
cout<<name[i]<<endl;
}
cout<<name[1];
return 0;
}
:::
P2045 方格取数加强版
还是拆点喵。
将每一个格子拆成入点和出点喵，两个点之间连边喵。
- 将 (i,j) 与 (i,j)' 连边 \{1,c_{i,j}\} 喵，这代表了首次经过这个格子有 c 的收益喵。
- 将 (i,j) 与 (i,j)' 连边 \{k-1,c_{i,j}\} 喵，这代表了经过一次之后，再经过这个格子没有收益了喵。k-1 是因为第一次已经过了一次了喵。
- 将 (i,j)' 与 (i,j+1),(i+1,j) 连边 \{k,0\} 喵。这代表了进行移动，且这个路径最多经过 k 次喵。
最后求出最大费用最大流喵。
:::info[code]
#include<bits/stdc++.h>
using namespace std;
const int maxn=10001,inf=INT_MAX;
int n,m,k,s,t,head[maxn],tot=2,dis[maxn],cur[maxn],val[maxn][maxn];//inqueue
struct edge{
int u,v,w,c,nxt;
}ed[maxn];
bool inq[maxn],vis[maxn];
queue<int> q;
void adde(int u,int v,int w,int c){
ed[tot]={u,v,w,c,head[u]};
head[u]=tot;
tot++;
}
bool spfa(){
for(int i=0;i<maxn;i++)dis[i]=-inf;
dis[s]=0;
inq[s]=1;
q.push(s);
while(q.size()){
int u=q.front();
q.pop();
inq[u]=0;
for(int i=head[u];i;i=ed[i].nxt){
int v=ed[i].v,c=ed[i].c,flow=ed[i].w;
if(dis[v]<dis[u]+c&&flow){
dis[v]=dis[u]+c;
if(!inq[v])q.push(v);
inq[v]=1;
}
}
}
return dis[t]!=-inf;
}
int dfs(int u,int cap){
int flow=0;
if(u==t)return cap;
vis[u]=1;
for(int i=cur[u];i&∩i=ed[i].nxt){
cur[u]=i;
int v=ed[i].v,c=ed[i].c,fl=ed[i].w;
if(dis[v]==dis[u]+c&&fl&&!vis[v]){
int use=dfs(v,min(cap,fl));
if(use>0){
ed[i].w-=use;
ed[i^1].w+=use;
flow+=use;
cap-=use;
}
}
}
vis[u]=0;
return flow;
}
pair<int,int> dinic(){
int flow=0,cost=0;
while(spfa()){
memcpy(cur,head,sizeof(head));
int fl=dfs(s,inf);
flow+=fl;
cost+=fl*dis[t];
}
return {flow,cost};
}
int id(int x,int y){
return (x-1)*n+y;
}
int id2(int x,int y){
return n*n+id(x,y);
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);
cin>>n>>k;
s=1;t=2*n*n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>val[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
adde(id(i,j),id2(i,j),1,val[i][j]);
adde(id2(i,j),id(i,j),0,-val[i][j]);
adde(id(i,j),id2(i,j),k-1,0);
adde(id2(i,j),id(i,j),0,0);
if(j<n)adde(id2(i,j),id(i,j+1),k,0);
if(j<n)adde(id(i,j+1),id2(i,j),0,0);
if(i<n)adde(id2(i,j),id(i+1,j),k,0);
if(i<n)adde(id(i+1,j),id2(i,j),0,0);
}
}
cout<<dinic().second;
return 0;
}
:::
网络流综合练习
P2774 方格取数问题
先染一下色。
\fcolorbox{black}{black}{\color{white}{1}} \fcolorbox{black}{white}{2} \fcolorbox{black}{black}{\color{white}{3}}\\ \fcolorbox{black}{white}{3} \fcolorbox{black}{black}{\color{white}{2}} \fcolorbox{black}{white}{3}\\ \fcolorbox{black}{black}{\color{white}{2}} \fcolorbox{black}{white}{3} \fcolorbox{black}{black}{\color{white}{1}}
可以发现，选择了一个黑色格子，就不能选择相邻的白色格子。
我们的思路大概出来了。
- 设 S 为所有黑点的集合，T 为所有白点的集合。
- 初始时所有黑点和相邻的白点连接，S,T 形成一个二分图。
- 我们需要选择集合 I 是独立集。I 包含黑点和白点，且互不干涉，满足要求。
由于最大权独立集 = 总价值 - 最小点权覆盖，又因为最小点权覆盖 = 最小割 = 最大流，所以我们只需跑一次最大流就行了。
:::info[code]
#include<bits/stdc++.h>
using namespace std;
const int maxn=10101,maxc=101,inf=INT_MAX;
struct edge{
int u,v,w,nxt;
}ed[maxn];
int tot=2,a[maxc][maxc],head[maxn],cur[maxn],lvl[maxn],s,t,n,m;
bool color[maxc][maxc];
void adde(int u,int v,int w){
ed[tot]={u,v,w,head[u]};
head[u]=tot;
tot++;
}
bool bfs(){
queue<int> q;
q.push(s);
for(int i=0;i<maxn;i++)lvl[i]=-1;
lvl[s]=0;
while(q.size()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=ed[i].nxt){
int v=ed[i].v,flow=ed[i].w;
if(flow&&lvl[v]==-1){
lvl[v]=lvl[u]+1;
q.push(v);
}
}
}
return lvl[t]!=-1;
}
int dfs(int u,int cap){
if(u==t)return cap;
int flow=0;
for(int i=cur[u];i&∩i=ed[i].nxt){
int v=ed[i].v,fl=ed[i].w;
cur[u]=i;
if(lvl[v]==lvl[u]+1){
int use=dfs(v,min(cap,fl));
if(use>0){
flow+=use;
cap-=use;
ed[i].w-=use;
ed[i^1].w+=use;
}
}
}
return flow;
}
int dinic(){
int flow=0;
while(bfs()){
memcpy(cur,head,sizeof(head));
flow+=dfs(s,inf);
}
return flow;
}
int id(int x,int y){
return (x-1)*n+y;
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);
cin>>m>>n;
s=0,t=m*n+1;
int sum=0;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
sum+=a[i][j];
color[i][j]=(i+j)%2;
}
}
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(color[i][j]){
adde(s,id(i,j),a[i][j]);
adde(id(i,j),s,0);
if(j<n)adde(id(i,j),id(i,j+1),inf);
if(j<n)adde(id(i,j+1),id(i,j),0);
if(j>1)adde(id(i,j),id(i,j-1),inf);
if(j>1)adde(id(i,j-1),id(i,j),0);
if(i<m)adde(id(i,j),id(i+1,j),inf);
if(i<m)adde(id(i+1,j),id(i,j),0);
if(i>1)adde(id(i,j),id(i-1,j),inf);
if(i>1)adde(id(i-1,j),id(i,j),0);
}
else{
adde(id(i,j),t,a[i][j]);
adde(t,id(i,j),0);
}
}
}
cout<<sum-dinic();
return 0;
}
:::
还有双倍经验 P4474 王者之剑。
P4012 深海机器人问题
考虑对于每一条边，建立一条边 \{1,w_{(i,j)\to(i,j+1)}\}，表示只能获得一次这个价值。同时建立 \{\infty,0\}，表示可以无限经过，但不能获得价值。
对于 (i,j)\to(i+1,j) 一样处理。
怎么处理出发点和结束点呢？
建立超级源点 s，既然有 k_i 个机器人从 (x_i,y_i) 出发，那就把 s\to (x_i,y_i) 建立 \{k_i,0\} 的边。
对于结束点，将结束点和 t 连起来就可以了。
:::info[code]
#include<bits/stdc++.h>
using namespace std;
const int maxn=5000,inf=INT_MAX;
int n,m,s,t,head[maxn],tot=2,dis[maxn],cur[maxn],a,b,p;//inqueue
struct edge{
int u,v,w,c,nxt;
}ed[maxn];
bool inq[maxn],vis[maxn];
void adde(int u,int v,int w,int c){
ed[tot]={u,v,w,c,head[u]};
head[u]=tot;
tot++;
}
bool spfa(){
queue<int> q;
for(int i=0;i<maxn;i++)dis[i]=-inf;
dis[s]=0;
inq[s]=1;
q.push(s);
while(q.size()){
int u=q.front();
q.pop();
inq[u]=0;
for(int i=head[u];i;i=ed[i].nxt){
int v=ed[i].v,c=ed[i].c,flow=ed[i].w;
if(dis[v]<dis[u]+c&&flow){
dis[v]=dis[u]+c;
if(!inq[v])q.push(v);
inq[v]=1;
}
}
}
return dis[t]!=-inf;
}
int dfs(int u,int cap){
int flow=0;
if(u==t)return cap;
vis[u]=1;
for(int i=cur[u];i&∩i=ed[i].nxt){
cur[u]=i;
int v=ed[i].v,c=ed[i].c,fl=ed[i].w;
if(dis[v]==dis[u]+c&&fl&&!vis[v]){
int use=dfs(v,min(cap,fl));
if(use>0){
ed[i].w-=use;
ed[i^1].w+=use;
flow+=use;
cap-=use;
}
}
}
vis[u]=0;
return flow;
}
pair<int,int> dinic(){
int flow=0,cost=0;
while(spfa()){
memcpy(cur,head,sizeof(head));
int fl=dfs(s,inf);
flow+=fl;
cost+=fl*dis[t];
}
return {flow,cost};
}
int id[40][40],idx=0;
signed main(){
int q;
ios::sync_with_stdio(0);cin.tie(0);
cin>>a>>b>>p>>q;
s=idx,t=++idx;
for(int i=0;i<=p;i++){
for(int j=0;j<=q;j++){
id[i][j]=++idx;
}
}
for(int i=0;i<=p;i++){
for(int j=0;j<q;j++){
int w;
cin>>w;
adde(id[i][j],id[i][j+1],1,w);
adde(id[i][j+1],id[i][j],0,-w);
adde(id[i][j],id[i][j+1],inf,0);
adde(id[i][j+1],id[i][j],0,0);
}
}
for(int i=0;i<=q;i++){
for(int j=0;j<p;j++){
int w;
cin>>w;
adde(id[j][i],id[j+1][i],1,w);
adde(id[j+1][i],id[j][i],0,-w);
adde(id[j][i],id[j+1][i],inf,0);
adde(id[j+1][i],id[j][i],0,0);
}
}
for(int i=1;i<=a;i++){
int k,x,y;
cin>>k>>x>>y;
adde(s,id[x][y],k,0);
adde(id[x][y],s,0,0);
}
for(int i=1;i<=b;i++){
int r,x,y;
cin>>r>>x>>y;
adde(id[x][y],t,r,0);
adde(t,id[x][y],0,0);
}
cout<<dinic().second;
return 0;
}
:::
P2762 太空飞行计划问题
挺有意思。其实和方格取数那道题有点相同，都是使用最小割来进行选择决策。
还是超源超汇，将 s 与实验连接，容量为 E_i，将仪器与 t 连接，容量为 I_i。中间再进行连接，容量为 \infty。
这里其实是把容量看成权值进行决策。
考虑证明答案最优。
设选出来的实验集合为 P，选出来的仪器集合为 Q
可以参考上面的图片，红色是割。
可以看到 $\sum\limits_{i\notin P}E_i-\sum\limits_{j\in Q}I_j$ 就是最小割容量 $Cut(G)$。（$\text{\color{green}{绿色}}$、$\text{\color{orange}{橙色}}$ 部分）
所以 $ans=\sum E-Cut(G)$。
:::info[code]
```cpp
#include<bits/stdc++.h>
using namespace std;
int m,n;
const int maxn=10001,inf=INT_MAX;
int lvl[maxn],tot=2,head[maxn],cur[maxn],s,t;
struct edge{
int u,v,w,nxt;
}ed[maxn];
void adde(int u,int v,int w){
ed[tot]={u,v,w,head[u]};
head[u]=tot;
tot++;
}
bool bfs(){
queue<int> q;
for(int i=0;i<maxn;i++)lvl[i]=-1;
lvl[s]=0;
q.push(s);
while(q.size()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=ed[i].nxt){
int v=ed[i].v,flow=ed[i].w;
if(lvl[v]==-1&&flow){
lvl[v]=lvl[u]+1;
q.push(v);
}
}
}
return lvl[t]!=-1;
}
int dfs(int u,int cap){
if(u==t)return cap;
int flow=0;
for(int i=cur[u];i&∩i=ed[i].nxt){
cur[u]=i;
int v=ed[i].v,fl=ed[i].w;
if(lvl[v]==lvl[u]+1){
int use=dfs(v,min(cap,fl));
if(use>0){
cap-=use;
flow+=use;
ed[i].w-=use;
ed[i^1].w+=use;
}
}
}
return flow;
}
void dinic(){
while(bfs()){
memcpy(cur,head,sizeof(head));
int tmp=dfs(s,inf);
}
}
int E[maxn],I[maxn];
signed main(){
//有m个实验，每个实验只可以进行一次，但会获得相应的奖金。
//有n个仪器，每个实验都需要一定的仪器，每个仪器可以运用于多个实验，但需要一定的价值。
//问奖金与代价的差的最大值是多少？
ios::sync_with_stdio(0);cin.tie(0);
cin>>m>>n;
string str;
s=0,t=n+m+1;
for(int i=1,p,id;i<=m;i++){
cin>>p;//p 为赞助商同意支付该实验的费用
E[i]=p;
getline(cin,str);
adde(s,i,p);
adde(i,s,0);
stringstream inpt(str);
while(inpt>>id){
adde(i,id+m,inf);
adde(id+m,i,0);
}
}
for(int i=1;i<=n;i++){
int p;
cin>>p;
adde(i+m,t,p);
adde(t,i+m,0);
I[i+m]=p;
}
//最小割选择点
dinic();
int g=0,k=0;
for(int i=head[s];i;i=ed[i].nxt){
if(lvl[ed[i].v]!=-1){
cout<<ed[i].v<<' ';
g+=E[ed[i].v];
}
}
cout<<endl;
for(int i=head[t];i;i=ed[i].nxt){
if(lvl[ed[i].v]!=-1){
cout<<ed[i].v-m<<' ';
k+=I[ed[i].v];
}
}
cout<<endl<<g-k;
return 0;
}
```
:::
### [P1251 餐巾计划问题](https://www.luogu.com.cn/problem/P1251)
将一天拆成两个点，$i+n$ 是早上，$i$ 是晚上。早上收到的都是**干净的餐巾**。
**为了方便表示，下面的 $n,m,s,t$ 不与题目中的相同。**
建立超级源点汇点 $s,t$。
对于一天：
- 晚上会产生 $need_i$ 的脏餐巾，于是将 $s$ 与 $i$ 建边 $\{need_i,0\}$。
- 早上需要 $need_i$ 的餐巾，于是将 $i+n$ 与 $t$ 建边 $\{need_i,0\}$，如果流满了，表示**足够用**。
- 快洗店：$i$ 天晚上送出餐巾，$i+day_f$ 天的早上（$i+n+day_f$）收到餐巾，于是将 $i$ 与 $i+n+day_f$ 连 $\{\infty,cost_f\}$ 的边。毕竟要花钱嘛。
- 慢洗店：$i$ 天晚上送出餐巾，$i+day_s$ 天的早上（$i+n+day_s$）收到餐巾，于是将 $i$ 与 $i+n+day_s$ 连 $\{\infty,cost_s\}$ 的边。
- 脏餐巾可以留到明天晚上，因为明天可能本来就能收到足够的干净餐巾。于是把 $i$ 与 $i+1$ 连一条 $\{\infty,0\}$ 的边。
- 最后，还可以早上直接买来干净毛巾，所以将 $s$ 与 $i+n$ 连接 $\{\infty,p\}$。
:::info[为什么要最小费用最大流]
必须要最大流量，才能把 $i+n\to t$ 的边流满，表示够用。
:::
:::info[code]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=200001,inf=INT_MAX;
int n,m,s,t,head[maxn],tot=2,dis[maxn],cur[maxn],a,b,p;//inqueue
struct edge{
int u,v,w,c,nxt;
}ed[maxn];
bool inq[maxn],vis[maxn];
void adde(int u,int v,int w,int c){
ed[tot]={u,v,w,c,head[u]};
head[u]=tot;
tot++;
}
bool spfa(){
queue<int> q;
for(int i=0;i<maxn;i++)dis[i]=inf;
dis[s]=0;
inq[s]=1;
q.push(s);
while(q.size()){
int u=q.front();
q.pop();
inq[u]=0;
for(int i=head[u];i;i=ed[i].nxt){
int v=ed[i].v,c=ed[i].c,flow=ed[i].w;
if(dis[v]>dis[u]+c&&flow){
dis[v]=dis[u]+c;
if(!inq[v])q.push(v);
inq[v]=1;
}
}
}
return dis[t]!=inf;
}
int dfs(int u,int cap){
int flow=0;
if(u==t)return cap;
vis[u]=1;
for(int i=cur[u];i&∩i=ed[i].nxt){
cur[u]=i;
int v=ed[i].v,c=ed[i].c,fl=ed[i].w;
if(dis[v]==dis[u]+c&&fl&&!vis[v]){
int use=dfs(v,min(cap,fl));
if(use>0){
ed[i].w-=use;
ed[i^1].w+=use;
flow+=use;
cap-=use;
}
}
}
vis[u]=0;
return flow;
}
pair<int,int> dinic(){
int flow=0,cost=0;
while(spfa()){
memcpy(cur,head,sizeof(head));
int fl=dfs(s,inf);
flow+=fl;
cost+=fl*dis[t];
}
return {flow,cost};
}
int nd[maxn],idx=0;
signed main(){
int q,k,d,f;
ios::sync_with_stdio(0);cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>nd[i];
cin>>p>>m>>f>>d>>k;
s=0;t=n*2+1;
for(int i=1;i<=n;i++){//i+n是早上，i是晚上
adde(s,i,nd[i],0);
adde(i,s,0,0);
adde(i+n,t,nd[i],0);
adde(t,i+n,0,0);
if(i+m<=n)adde(i,i+n+m,inf,f);
if(i+m<=n)adde(i+n+m,i,0,-f);
if(i+d<=n)adde(i,i+n+d,inf,k);
if(i+d<=n)adde(i+n+d,i,0,-k);
adde(s,i+n,inf,p);
adde(i+n,s,0,-p);
if(i+1<=n)adde(i,i+1,inf,0);
if(i+1<=n)adde(i+1,i,0,0);
}
cout<<dinic().second;
return 0;
}
```
:::
### [P4013 数字梯形问题](https://www.luogu.com.cn/problem/P4013)
这题太水了，降降降，蓝吧。
还是先建立超源超汇。
规则 1：将点拆成入点和出点，连边 $\{1,c_{i,j}\}$，表示只能经过一次。
规则 2：不用拆点了，边的容量设为 $1$，点权转边权即可。
规则 3：……太水了吧，容量 $\infty$。
就是注意清空。
:::info[code]
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=10010,inf=INT_MAX;
int s,t,head[maxn],tot=2,dis[maxn],cur[maxn];
struct edge{
int u,v,w,c,nxt;
}ed[maxn];
bool vis[maxn],inq[maxn];
void adde(int u,int v,int w,int c){
ed[tot]={u,v,w,c,head[u]};
head[u]=tot;
tot++;
}
bool spfa(){
for(int i=0;i<maxn;i++)dis[i]=-inf;
queue<int> q;
q.push(s);
inq[s]=1;
dis[s]=0;
while(q.size()){
int u=q.front();
q.pop();
inq[u]=0;
for(int i=head[u];i;i=ed[i].nxt){
int v=ed[i].v,flow=ed[i].w,c=ed[i].c;
if(dis[v]<dis[u]+c&&flow){
dis[v]=dis[u]+c;
if(!inq[v])q.push(v);
}
}
}
return dis[t]!=-inf;
}
int dfs(int u,int cap){
if(u==t)return cap;
int flow=0;
vis[u]=1;
for(int i=cur[u];i&∩i=ed[i].nxt){
cur[u]=i;
int v=ed[i].v,fl=ed[i].w,c=ed[i].c;
if(dis[v]==dis[u]+c&&fl&&!vis[v]){
int use=dfs(v,min(cap,fl));
if(use>0){
ed[i].w-=use;
ed[i^1].w+=use;
cap-=use;
flow+=use;
}
}
}
vis[u]=0;
return flow;
}
pair<int,int> dinic(){
int flow=0,cost=0;
while(spfa()){
memcpy(cur,head,sizeof(head));
int fl=dfs(s,inf);
flow+=fl;
cost+=fl*dis[t];
}
return {flow,cost};
}
void reset(){
tot=2;
memset(head,0,sizeof(head));
memset(cur,0,sizeof(cur));
for(int i=0;i<maxn;i++)ed[i]={0,0,0,0,0};
}
int num[40][40],n,m,idx=0,id[40][40];
signed main(){
ios::sync_with_stdio(0);cin.tie(0);
cin>>m>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=m+i-1;j++){
cin>>num[i][j];
id[i][j]=++idx;
}
}
s=0;
for(int i=1;i<=m;i++){
adde(s,id[1][i],1,0);
adde(id[1][i],s,0,0);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m+i-1;j++){
adde(id[i][j],id[i][j]+idx,1,num[i][j]);
adde(id[i][j]+idx,id[i][j],0,-num[i][j]);
if(i<n)adde(id[i][j]+idx,id[i+1][j],1,0);
if(i<n)adde(id[i+1][j],id[i][j]+idx,0,0);
if(i<n)adde(id[i][j]+idx,id[i+1][j+1],1,0);
if(i<n)adde(id[i+1][j+1],id[i][j]+idx,0,0);
}
}
t=idx*2+1;
for(int i=1;i<=m+n-1;i++){
adde(id[n][i]+idx,t,inf,0);
adde(t,id[n][i]+idx,0,0);
}
cout<<dinic().second<<endl;
//____________________________________________
reset();
for(int i=1;i<=m;i++){
adde(s,id[1][i],1,0);
adde(id[1][i],s,0,0);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m+i-1;j++){
if(i<n)adde(id[i][j],id[i+1][j],1,num[i][j]);
if(i<n)adde(id[i+1][j],id[i][j],0,-num[i][j]);
if(i<n)adde(id[i][j],id[i+1][j+1],1,num[i][j]);
if(i<n)adde(id[i+1][j+1],id[i][j],0,-num[i][j]);
}
}
t=idx+1;
for(int i=1;i<=m+n-1;i++){
adde(id[n][i],t,inf,num[n][i]);
adde(t,id[n][i],0,-num[n][i]);
}
cout<<dinic().second<<endl;
//____________________________________________
reset();
for(int i=1;i<=m;i++){
adde(s,id[1][i],1,0);
adde(id[1][i],s,0,0);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m+i-1;j++){
if(i<n)adde(id[i][j],id[i+1][j],inf,num[i][j]);
if(i<n)adde(id[i+1][j],id[i][j],0,-num[i][j]);
if(i<n)adde(id[i][j],id[i+1][j+1],inf,num[i][j]);
if(i<n)adde(id[i+1][j+1],id[i][j],0,-num[i][j]);
}
}
t=idx+1;
for(int i=1;i<=m+n-1;i++){
adde(id[n][i],t,inf,num[n][i]);
adde(t,id[n][i],0,-num[n][i]);
}
cout<<dinic().second;
return 0;
}
```
:::
### [P2765 魔术球问题](https://www.luogu.com.cn/problem/P2765)
双倍经验：[UVA10276 Hanoi Tower Troubles Again!](https://www.luogu.com.cn/problem/UVA10276)
::::info[题解]{open}
## [UVA10276 Hanoi Tower Troubles Again!](https://www.luogu.com.cn/problem/UVA10276)
前置知识：[P2764 最小路径覆盖问题](https://www.luogu.com.cn/problem/P2764)。
双倍经验：[P2765 魔术球问题](https://www.luogu.com.cn/problem/P2765)。~~这俩编号怎么只相差一。~~
## 分析
### Part 1：如何建模
我们考虑对于数 $i,j(i<j)$，如果 $i+j$ 是完全平方数，那么就连边。
可以发现这就是构成了一个有向无环图。
### Part 2：如何根据球的数量计算柱子
其实，这就是一个最小路径覆盖。
让我们看样例的**一个**构造方案：
```cpp
11
1 8
2 7 9
3 6 10
4 5 11
```
看出来了吗，这些颜色就是柱子上放的数！
当然，还有另一种构造方案：
其中 1 号点颜色不同。
### Part 3：如何计算路径覆盖
~~由于我们懒得写网络流~~，于是我们翻出了匈牙利。
参见我写的：[【最小路径覆盖问题】](https://www.cnblogs.com/luogu-article/articles/19234660)。
我们先进行拆点，将 $u$ 拆成 $u_{in},u_{out}$。
根据 Dilworth 推广定理：最小路径覆盖数 = 顶点数 − 最大匹配数。
所以我们只需要跑二分图最大匹配了。
```cpp
for(int i=0;i<m;i++){
int u,v;
cin>>u>>v;
G[u].push_back(v);//这里实际上是拆点了
}
```
为什么这里拆点了呢？其实左边的 $u$ 是 $u_{out}$，$v$ 就是 $v_{in}$。
### Part 4：如何根据柱子的数量计算球
考虑二分球的数量。与 $n$ 比较大小即可。
```cpp
bool check(int mid){
if(solve(mid)<=n)return 1;
return 0;
}
```
```cpp
int l=1,r=M,mid;
while(l<=r){
mid=(l+r)>>1;
if(check(mid))l=mid+1,now=mid;
else r=mid-1;
// cout<<l<<' '<<r<<endl;
}
if(check(now-1))now++;
if(!check(now-1))now--;
cout<<now-1<<endl;
```
我们发现边数大约为 $O(n^{3/2})$，所以时间复杂度大约 $O(n^{5/2}\log M)$，$V$ 可以取 $2000$。
当然你也可以不二分，直接枚举到 $V$，然后每次只加上新增的边跑二分图，这样是 $O(n^{3/2}V)$ 的。
:::info[code]
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=10000;
bool matched[maxn];
vector<int> G[maxn];
int match[maxn];
bool find(int u){
for(auto v:G[u]){
if(!matched[v]){
matched[v]=1;
if(!match[v]||find(match[v])){
match[v]=u;
return 1;
}
}
}
return 0;
}
const int M=10000;
bool pd[M];
int solve(int ma){//根据球数算柱子
for(int i=0;i<maxn;i++)G[i].clear();
for(int i=1;i<=ma;i++){
for(int j=i+1;j<=ma;j++){
if((int)sqrt(i+j)*(int)sqrt(i+j)==i+j){
G[i].push_back(j);//这里实际上是拆点了
}
}
}
int ans=0;
memset(match,0,sizeof(match));
for(int i=1;i<=ma;i++){
memset(matched,0,sizeof(matched));
if(find(i))ans++;
}
return ma-ans;
}
int pre[maxn],nxt[maxn],n;
bool vis[maxn];
bool check(int mid){
if(solve(mid)<=n)return 1;
return 0;
}
signed main(){
int now=1;
cin>>n;
int l=1,r=M,mid;
while(l<=r){
mid=(l+r)>>1;
if(check(mid))l=mid+1,now=mid;
else r=mid-1;
// cout<<l<<' '<<r<<endl;
}
if(check(now-1))now++;
if(!check(now-1))now--;
cout<<now-1<<endl;
// for(int v=1;v<=now-1;v++){
// int u=match[v];
// if(u){
// nxt[u]=v;
// pre[v]=u;
// }
// }
// memset(vis,0,sizeof(vis));//标记顶点是否已被包含在路径中
// vector<vector<int>>paths;//存储最终的所有路径
// for(int u=1;u<=now-1;u++){
// if(pre[u]==0){
// vector<int> path;
// int v=u;
// while(v){
// vis[v]=1;
// path.push_back(v);
// v=nxt[v];
// }
// paths.push_back(path);
// }
// }
// for(auto &path:paths){
// for(int i=0;i<path.size();i++){
// cout<<path[i]<<' ';
// }
// cout<<endl;
// }
return 0;
}
```
:::
### Part 5：优化
还是上网络流。这样单轮时间复杂度是 $O(m\sqrt n)=O(n^{3/2}\cdot n^{1/2})=O(n^2)$，总计 $O(n^2\log V)$，完全可过。
:::info[code]
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=5055,M=125005,inf=2147483647;
int m,s,t;
int lvl[N];//层数
struct edge{
int u,v,w;
int nxt;
}ed[M*2];
int head[N],cur[N],cnt=2;
void adde(int u,int v,int w){
ed[cnt].u=u;
ed[cnt].v=v;
ed[cnt].w=w;
ed[cnt].nxt=head[u];
head[u]=cnt;
cnt++;
}
bool bfs(){
queue<int> q;
for(int i=0;i<N;i++)lvl[i]=-1;
lvl[s]=0;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=ed[i].nxt){
if(lvl[ed[i].v]==-1&&ed[i].w>0){
lvl[ed[i].v]=lvl[u]+1;
q.push(ed[i].v);
if(ed[i].v==t)return 1;
}
}
}
return(lvl[t]!=-1);
}
int dfs(int u,int cap){//cap:容量
int flow=0;//跑过的流
if(u==t)return cap;
for(int i=cur[u];i&∩i=ed[i].nxt){
cur[u]=i;
int v=ed[i].v,w=ed[i].w;
if(w&&lvl[v]==lvl[u]+1){
int use=dfs(v,min(cap,w));
if(use==0)lvl[v]=-1;
if(use>0){
ed[i].w-=use;
ed[i^1].w+=use;
cap-=use;
flow+=use;
}
}
}
return flow;
}
int dinic(){
int ans=0;
while(bfs()){
memcpy(cur,head,sizeof(head));
ans+=dfs(s,inf);
}
return ans;
}
const int MM=2000;
bool pd[M];
int solve(int ma){//根据球数算柱子
s=0,t=ma*2+1;
cnt=2;
memset(head,0,sizeof(head));
memset(cur,0,sizeof(cur));
for(int i=1;i<=ma;i++){
adde(s,i,1);
adde(i,s,0);
adde(i+ma,t,1);
adde(t,i+ma,0);
for(int j=i+1;j<=ma;j++){
if((int)sqrt(i+j)*(int)sqrt(i+j)==i+j){
adde(i,j+ma,1);
adde(j+ma,i,0);
}
}
}
return ma-dinic();
}
int pre[M],nxt[M],n;
bool vis[M];
bool check(int mid){
if(solve(mid)<=n)return 1;
return 0;
}
signed main(){
int now=1;
cin>>n;
int l=1,r=MM,mid;
while(l<=r){
mid=(l+r)>>1;
if(check(mid))l=mid+1,now=mid;
else r=mid-1;
// cout<<l<<' '<<r<<endl;
}
if(check(now-1))now++;
if(!check(now-1))now--;
cout<<now-1<<endl;
return 0;
}
```
:::
::::
### [P1361 小M的作物](https://www.luogu.com.cn/problem/P1361)
首先，我们先不考虑特殊组合，如果仅仅是作物 $i$ 放在 $A$ 上获得 $a_i$ 的收益，放在 $B$上获得 $b_i$ 的收益，如何建图？
这时，可以从 $A$ 到 $i$ 点连一条边，权值为 $a_i$，然后 $i$ 向 $B$ 连一条边，权值为 $b_i$，这时利用最小割切割一下，就表示 $i$ 要么放在 $A$ 上，要么放在 $B$ 上，与题意相符，针对样例，如下图：
我们有了上面的方法之后，想到，可以为每一个组合建立两个虚拟节点 $X,Y$，分别与所包含的作物连边 $\{\infty\}$。（这是为了**保证无法被切割**，组合被切开你还想要拿 $c_{i,1},c_{i,2}$ 简直是痴心妄想）其中，一个组合节点 $X_i$ 与 $s$ 连边表示选了组合方法 $1$，$Y_i$ 与 $t$ 连边表示选了组合方法 $2$。
**下面解释为什么不能只建一个节点：**
考虑只建一个节点。
显然是不选择组合的。
但是你又无法同时割掉 $0\to4,4\to5$。这样不满足最小割的定义。
这根本不能割啊。
:::info[code]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5,inf=1e18;
struct edge{
int u,v,w,nxt;
}ed[maxn*10];
int head[maxn],cur[maxn],tot=2,lvl[maxn],s,t,a[maxn],b[maxn];//head:上一个
void adde(int u,int v,int w){
ed[tot]={u,v,w,head[u]};
head[u]=tot;
tot++;
}
bool bfs(){
queue<int> q;
for(int i=0;i<maxn;i++)lvl[i]=-1;
lvl[s]=0;
q.push(s);
while(q.size()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=ed[i].nxt){
int v=ed[i].v,flow=ed[i].w;
if(lvl[v]==-1&&flow){
lvl[v]=lvl[u]+1;
q.push(v);
}
}
}
return lvl[t]!=-1;
}
int dfs(int u,int cap){
if(u==t)return cap;
int flow=0;
for(int i=cur[u];i&∩i=ed[i].nxt){
cur[u]=i;
int v=ed[i].v,fl=ed[i].w;
if(lvl[v]==lvl[u]+1&&fl){
int use=dfs(v,min(cap,fl));
if(use>0){
flow+=use;
cap-=use;
ed[i].w-=use;
ed[i^1].w+=use;
}
}
}
return flow;
}
int dinic(){
int ans=0;
while(bfs()){
memcpy(cur,head,sizeof(head));
ans+=dfs(s,inf);
}
return ans;
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);
int nn,mm,sum=0;
cin>>nn;
s=0;
for(int i=1;i<=nn;i++){
cin>>a[i];
adde(s,i,a[i]);
adde(i,s,0);
sum+=a[i];
}
for(int i=1;i<=nn;i++){
cin>>b[i];
sum+=b[i];
}
cin>>mm;
t=nn+mm*2+1;
for(int i=1;i<=nn;i++){
adde(i,t,b[i]);
adde(t,i,0);
}
int idx=nn+1;
for(int i=1;i<=mm;i++){
int k,c1,c2;
cin>>k>>c1>>c2;
adde(s,idx,c1);
adde(idx,s,0);
for(int j=1;j<=k;j++){
int id;
cin>>id;
adde(idx,id,inf);
adde(id,idx,0);
adde(id,idx+1,inf);
adde(idx+1,id,0);
}
adde(idx+1,t,c2);
adde(t,idx+1,0);
idx+=2;
sum+=c1+c2;
}
cout<<sum-dinic();
return 0;
}
```
:::
### [P4313 文理分科](https://www.luogu.com.cn/problem/P4313)
这个和小 M 的作物很像。就是相当于把自己和周围同学捆绑成一个组合，建图还是和小 M 的作物一样。
:::info[code]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5,inf=1e18;
struct edge{
int u,v,w,nxt;
}ed[maxn*10];
int head[maxn],cur[maxn],tot=2,lvl[maxn],s,t,a[maxn],b[maxn],n,m;//head:上一个
void adde(int u,int v,int w){
ed[tot]={u,v,w,head[u]};
head[u]=tot;
tot++;
}
bool bfs(){
queue<int> q;
for(int i=0;i<maxn;i++)lvl[i]=-1;
lvl[s]=0;
q.push(s);
while(q.size()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=ed[i].nxt){
int v=ed[i].v,flow=ed[i].w;
if(lvl[v]==-1&&flow){
lvl[v]=lvl[u]+1;
q.push(v);
}
}
}
return lvl[t]!=-1;
}
int dfs(int u,int cap){
if(u==t)return cap;
int flow=0;
for(int i=cur[u];i&∩i=ed[i].nxt){
cur[u]=i;
int v=ed[i].v,fl=ed[i].w;
if(lvl[v]==lvl[u]+1&&fl){
int use=dfs(v,min(cap,fl));
if(use>0){
flow+=use;
cap-=use;
ed[i].w-=use;
ed[i^1].w+=use;
}
}
}
return flow;
}
int dinic(){
int ans=0;
while(bfs()){
memcpy(cur,head,sizeof(head));
ans+=dfs(s,inf);
}
return ans;
}
int id[110][110],idx=0,sum=0;
signed main(){
ios::sync_with_stdio(0);cin.tie(0);
cin>>n>>m;
s=0;
t=n*m*4+1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
id[i][j]=++idx;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int art;
cin>>art;
sum+=art;
adde(s,id[i][j],art);
adde(id[i][j],s,0);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int sci;
cin>>sci;
sum+=sci;
adde(id[i][j],t,sci);
adde(t,id[i][j],0);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int sma;
cin>>sma;
sum+=sma;
int nw=++idx;
adde(s,nw,sma);
adde(nw,s,0);
adde(nw,id[i][j],inf);
adde(id[i][j],nw,0);
if(j<m)adde(nw,id[i][j+1],inf);
if(j<m)adde(id[i][j+1],nw,0);
if(j>1)adde(nw,id[i][j-1],inf);
if(j>1)adde(id[i][j-1],nw,0);
if(i<n)adde(nw,id[i+1][j],inf);
if(i<n)adde(id[i+1][j],nw,0);
if(i>1)adde(nw,id[i-1][j],inf);
if(i>1)adde(id[i-1][j],nw,0);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int smc;
cin>>smc;
sum+=smc;
int nw=++idx;
adde(nw,t,smc);
adde(t,nw,0);
adde(id[i][j],nw,smc);
adde(nw,id[i][j],0);
if(j<m)adde(id[i][j+1],nw,inf);
if(j<m)adde(nw,id[i][j+1],0);
if(j>1)adde(id[i][j-1],nw,inf);
if(j>1)adde(nw,id[i][j-1],0);
if(i<n)adde(id[i+1][j],nw,inf);
if(i<n)adde(nw,id[i+1][j],0);
if(i>1)adde(id[i-1][j],nw,inf);
if(i>1)adde(nw,id[i-1][j],0);
}
}
cout<<sum-dinic();
return 0;
}
```
:::
### [P1646 [国家集训队] happiness](https://www.luogu.com.cn/problem/P1646)
相当于双倍经验吧，只是把组合拆开了。
:::info[code]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5,inf=1e18;
struct edge{
int u,v,w,nxt;
}ed[maxn*10];
int head[maxn],cur[maxn],tot=2,lvl[maxn],s,t,a[maxn],b[maxn],n,m;//head:上一个
void adde(int u,int v,int w){
ed[tot]={u,v,w,head[u]};
head[u]=tot;
tot++;
}
bool bfs(){
queue<int> q;
for(int i=0;i<maxn;i++)lvl[i]=-1;
lvl[s]=0;
q.push(s);
while(q.size()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=ed[i].nxt){
int v=ed[i].v,flow=ed[i].w;
if(lvl[v]==-1&&flow){
lvl[v]=lvl[u]+1;
q.push(v);
}
}
}
return lvl[t]!=-1;
}
int dfs(int u,int cap){
if(u==t)return cap;
int flow=0;
for(int i=cur[u];i&∩i=ed[i].nxt){
cur[u]=i;
int v=ed[i].v,fl=ed[i].w;
if(lvl[v]==lvl[u]+1&&fl){
int use=dfs(v,min(cap,fl));
if(use>0){
flow+=use;
cap-=use;
ed[i].w-=use;
ed[i^1].w+=use;
}
}
}
return flow;
}
int dinic(){
int ans=0;
while(bfs()){
memcpy(cur,head,sizeof(head));
ans+=dfs(s,inf);
}
return ans;
}
int id[110][110],idx=0,sum=0;
signed main(){
ios::sync_with_stdio(0);cin.tie(0);
cin>>n>>m;
s=0;
t=n*m*6+1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
id[i][j]=++idx;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int art;
cin>>art;
sum+=art;
adde(s,id[i][j],art);
adde(id[i][j],s,0);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int sci;
cin>>sci;
sum+=sci;
adde(id[i][j],t,sci);
adde(t,id[i][j],0);
}
}
for(int i=1;i<n;i++){
for(int j=1;j<=m;j++){
int val,nw=++idx;
cin>>val;
sum+=val;
adde(nw,id[i][j],inf);
adde(id[i][j],nw,0);
adde(nw,id[i+1][j],inf);
adde(id[i+1][j],nw,0);
adde(s,nw,val);
adde(nw,s,0);
}
}
for(int i=1;i<n;i++){
for(int j=1;j<=m;j++){
int val,nw=++idx;
cin>>val;
sum+=val;
adde(id[i][j],nw,inf);
adde(nw,id[i][j],0);
adde(id[i+1][j],nw,inf);
adde(nw,id[i+1][j],0);
adde(nw,t,val);
adde(t,nw,0);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<m;j++){
int val,nw=++idx;
cin>>val;
sum+=val;
adde(nw,id[i][j],inf);
adde(id[i][j],nw,0);
adde(nw,id[i][j+1],inf);
adde(id[i][j+1],nw,0);
adde(s,nw,val);
adde(nw,s,0);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<m;j++){
int val,nw=++idx;
cin>>val;
sum+=val;
adde(id[i][j],nw,inf);
adde(nw,id[i][j],0);
adde(id[i][j+1],nw,inf);
adde(nw,id[i][j+1],0);
adde(nw,t,val);
adde(t,nw,0);
}
}
cout<<sum-dinic();
return 0;
}
```
:::
### [P2057 [SHOI2007] 善意的投票 / [JLOI2010] 冠军调查](https://www.luogu.com.cn/problem/P2057)
将同意的与 $s$ 连容量为 $1$ 的边，不同意的就和 $t$ 连接。
为什么要双向边？因为 $u,v$ 互斥的话，可以是 $v$ 违反自己意愿，也可以 $u$ 违反自己意愿。
:::info[code]
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=109310,inf=INT_MAX;
int lvl[maxn],head[maxn],cur[maxn],tot=2,s,t;
struct edge{
int u,v,w,nxt;
}ed[maxn];
void adde(int u,int v,int w){
ed[tot]={u,v,w,head[u]};
head[u]=tot;
tot++;
}
bool bfs(){
queue<int> q;
for(int i=0;i<maxn;i++)lvl[i]=-1;
lvl[s]=0;
q.push(s);
while(q.size()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=ed[i].nxt){
int v=ed[i].v,flow=ed[i].w;
if(lvl[v]==-1&&flow){
lvl[v]=lvl[u]+1;
q.push(v);
}
}
}
return lvl[t]!=-1;
}
int dfs(int u,int cap){
int flow=0;
if(u==t)return cap;
for(int i=cur[u];i&∩i=ed[i].nxt){
cur[u]=i;
int v=ed[i].v,fl=ed[i].w;
if(lvl[v]==lvl[u]+1&&fl){
int use=dfs(v,min(cap,fl));
if(use>0){
flow+=use;
cap-=use;
ed[i].w-=use;
ed[i^1].w+=use;
}
}
}
return flow;
}
int dinic(){
int flow=0;
while(bfs()){
memcpy(cur,head,sizeof(head));
flow+=dfs(s,inf);
}
return flow;
}
bool agr[maxn];
signed main(){
ios::sync_with_stdio(0);cin.tie(0);
int n,m;
cin>>n>>m;
s=0;t=n+1;
for(int i=1;i<=n;i++){
cin>>agr[i];
if(agr[i]){
adde(s,i,1);
adde(i,s,0);
}
else{
adde(i,t,1);
adde(t,i,0);
}
}
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
adde(u,v,1);
adde(v,u,0);
adde(v,u,1);
adde(u,v,0);
}
cout<<dinic();
return 0;
}
```
:::
:::info[为什么错误]
不建双向边，只能统计到 $v$ 违反自己意愿和 $u$ 违反自己意愿这两个中的一个，所以答案错误。
:::
:::error[错误代码！虽然目前数据能 AC]{open}
upd：我自己交了 hack。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=59310,inf=INT_MAX;
int lvl[maxn],head[maxn],cur[maxn],tot=2,s,t;
struct edge{
int u,v,w,nxt;
}ed[maxn];
void adde(int u,int v,int w){
ed[tot]={u,v,w,head[u]};
head[u]=tot;
tot++;
}
bool bfs(){
queue<int> q;
for(int i=0;i<maxn;i++)lvl[i]=-1;
lvl[s]=0;
q.push(s);
while(q.size()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=ed[i].nxt){
int v=ed[i].v,flow=ed[i].w;
if(lvl[v]==-1&&flow){
lvl[v]=lvl[u]+1;
q.push(v);
}
}
}
return lvl[t]!=-1;
}
int dfs(int u,int cap){
int flow=0;
if(u==t)return cap;
for(int i=cur[u];i&∩i=ed[i].nxt){
cur[u]=i;
int v=ed[i].v,fl=ed[i].w;
if(lvl[v]==lvl[u]+1&&fl){
int use=dfs(v,min(cap,fl));
if(use>0){
flow+=use;
cap-=use;
ed[i].w-=use;
ed[i^1].w+=use;
}
}
}
return flow;
}
int dinic(){
int flow=0;
while(bfs()){
memcpy(cur,head,sizeof(head));
flow+=dfs(s,inf);
}
return flow;
}
bool agr[maxn];
signed main(){
ios::sync_with_stdio(0);cin.tie(0);
int n,m;
cin>>n>>m;
s=0;t=n+1;
for(int i=1;i<=n;i++){
cin>>agr[i];
if(agr[i]){
adde(s,i,1);
adde(i,s,0);
}
else{
adde(i,t,1);
adde(t,i,0);
}
}
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
if(agr[v]&&!agr[u])swap(u,v);
adde(u,v,1);
adde(v,u,0);
// adde(v,u,1);
// adde(u,v,0);
}
cout<<dinic();
return 0;
}
```
:::
### [P2598 [ZJOI2009] 狼和羊的故事](https://www.luogu.com.cn/problem/P2598)
将 $s$ 与狼连接，将羊与 $t$ 连接，连接容量都为 $\infty$，表示这个格子就是狼/羊的，不能分开，最小割不可能割掉 $\infty$。
对于一个格子，和四周连边，如果割开了，就表示修栅栏。
最后最小割会把图分为两部分，一部分属于狼，一部分属于羊，之间没有连接，符合要求。
:::info[code]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=109310,inf=INT_MAX;
int lvl[maxn],head[maxn],cur[maxn],tot=2,s,t;
struct edge{
int u,v,w,nxt;
}ed[maxn];
void adde(int u,int v,int w){
ed[tot]={u,v,w,head[u]};
head[u]=tot;
tot++;
}
bool bfs(){
queue<int> q;
for(int i=0;i<maxn;i++)lvl[i]=-1;
lvl[s]=0;
q.push(s);
while(q.size()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=ed[i].nxt){
int v=ed[i].v,flow=ed[i].w;
if(lvl[v]==-1&&flow){
lvl[v]=lvl[u]+1;
q.push(v);
}
}
}
return lvl[t]!=-1;
}
int dfs(int u,int cap){
int flow=0;
if(u==t)return cap;
for(int i=cur[u];i&∩i=ed[i].nxt){
cur[u]=i;
int v=ed[i].v,fl=ed[i].w;
if(lvl[v]==lvl[u]+1&&fl){
int use=dfs(v,min(cap,fl));
if(use>0){
flow+=use;
cap-=use;
ed[i].w-=use;
ed[i^1].w+=use;
}
}
}
return flow;
}
int dinic(){
int flow=0;
while(bfs()){
memcpy(cur,head,sizeof(head));
flow+=dfs(s,inf);
}
return flow;
}
int n,m;
int ld[110][110];
int id(int x,int y){
return (x-1)*m+y;
}
void add(int u,int v,int w){
adde(u,v,w);
adde(v,u,0);
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);
cin>>n>>m;
s=0;t=n*m+1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>ld[i][j];
if(ld[i][j]==1)add(s,id(i,j),inf);
else if(ld[i][j]==2)add(id(i,j),t,inf);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(i<n)add(id(i,j),id(i+1,j),1);
if(i>1)add(id(i,j),id(i-1,j),1);
if(j<m)add(id(i,j),id(i,j+1),1);
if(j>1)add(id(i,j),id(i,j-1),1);
}
}
cout<<dinic();
return 0;
}
```
:::
### [P2472 [SCOI2007] 蜥蜴](https://www.luogu.com.cn/problem/P2472)
我们考虑一个格子，每个格子只能经过 $h_{i,j}$ 次，因此拆点。
将 $s$ 与蜥蜴的格子连边 $1$，表示有一只蜥蜴。
对于能够跳到的格子（$dis\le d$）我们直接连边，边权为 $\infty$。
:::info[code]
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1205,M=15005,inf=2147483647;
int n,m,s,t,r,c;
int lvl[N];//层数
struct edge{
int u,v,w;
int nxt;
}ed[M*2];
int head[N],cur[N],cnt=2;
void adde(int u,int v,int w){
ed[cnt].u=u;
ed[cnt].v=v;
ed[cnt].w=w;
ed[cnt].nxt=head[u];
head[u]=cnt;
cnt++;
}
bool bfs(){
queue<int> q;
for(int i=0;i<N;i++)lvl[i]=-1;
lvl[s]=0;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=ed[i].nxt){
if(lvl[ed[i].v]==-1&&ed[i].w>0){
lvl[ed[i].v]=lvl[u]+1;
q.push(ed[i].v);
if(ed[i].v==t)return 1;
}
}
}
return(lvl[t]!=-1);
}
int dfs(int u,int cap){//cap:容量
int flow=0;//跑过的流
if(u==t)return cap;
for(int i=cur[u];i&∩i=ed[i].nxt){
cur[u]=i;
int v=ed[i].v,w=ed[i].w;
if(w&&lvl[v]==lvl[u]+1){
int use=dfs(v,min(cap,w));
if(use==0)lvl[v]=-1;
if(use>0){
ed[i].w-=use;
ed[i^1].w+=use;
cap-=use;
flow+=use;
}
}
}
return flow;
}
int dinic(){
int ans=0;
while(bfs()){
memcpy(cur,head,sizeof(head));
ans+=dfs(s,inf);
}
return ans;
}
int h[21][21],d,zz[21][21];
int id(int x,int y){
if(x<1||y<1||x>r||y>c)return t;
return (x-1)*c+y;
}
void add(int u,int v,int w){
adde(u,v,w);
adde(v,u,0);
}
void connect(int x,int y,int X,int Y){
int now=id(x,y)+r*c,nx=id(X,Y);
if(nx!=t){
if(!zz[X][Y])return;
}
add(now,nx,inf);
}
#define con(dx,dy) connect(i,j,i+dx,j+dy)
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>r>>c>>d;
s=0,t=r*c*2+1;
for(int i=1;i<=r;i++){
string ss;
cin>>ss;
for(int j=1;j<=c;j++){
char he=ss[j-1];
if(he!='0'){
zz[i][j]=he-'0';
}
}
}
for(int i=1;i<=r;i++){
for(int j=1;j<=c;j++){
if(zz[i][j]){
add(id(i,j),id(i,j)+r*c,zz[i][j]);
if(i==1||j==1||i==r||j==c)add(id(i,j)+r*c,t,inf);
if(d>=1){
con(1,0);
con(-1,0);
con(0,1);
con(0,-1);
}
if(d>=2){
con(2,0);
con(1,1);
con(0,2);
con(-1,1);
con(-2,0);
con(-1,-1);
con(0,-2);
con(1,-1);
}
if(d>=3){
con(3,0);
con(2,1);
con(2,2);
con(1,2);
con(0,3);
con(-1,2);
con(-2,2);
con(-2,1);
con(-3,0);
con(-2,-1);
con(-2,-2);
con(-1,-2);
con(0,-3);
con(1,-2);
con(2,-2);
}
if(d>=4){
con(4,0);
con(3,1);
con(3,2);
con(2,3);
con(1,3);
con(0,4);
con(-1,3);
con(-2,3);
con(-3,2);
con(-3,1);
con(-4,0);
con(-3,-1);
con(-3,-2);
con(-2,-3);
con(-1,-3);
con(0,-4);
con(1,-3);
con(2,-3);
con(3,-2);
con(3,-1);
}
}
}
}
int lz=0;
for(int i=1;i<=r;i++){
for(int j=1;j<=c;j++){
char ch;
cin>>ch;
if(ch=='L'){
lz++;
add(s,id(i,j),1);
}
}
}
cout<<lz-dinic();
return 0;
}
```
:::
### [P4174 [NOI2006] 最大获利](https://www.luogu.com.cn/problem/P4174) 与 [SP1476 PROFIT](https://www.luogu.com.cn/problem/SP1476)
类似 [P2762 太空飞行计划问题](https://www.luogu.com.cn/problem/P2762)，但是放一个题解吧。
首先我们来看题目。每个用户依赖 $A_i,B_i$，然后可以获得 $C_i$ 的价格。
还是超源超汇，将 $s$ 与服务站连接，容量为 $p_i$，将顾客与 $t$ 连接，将顾客和需要的服务站连接，容量为 $c_i$。中间再进行连接，将 容量为 $\infty$。
这里其实是把容量看成权值进行决策。
考虑证明答案最优。
设选出来的人集合为 $P$，选出来的服务站集合为 $Q
可以参考上面的图片，红色是割。
可以看到 $\sum\limits_{i\notin P}p_i+\sum\limits_{j\in Q}c_j$ 就是最小割容量 $Cut(G)$。（绿色，橙色部分）
所以 $ans=\sum p-Cut(G)$，最小化割即可。
:::info[code]
```cpp
#include<bits/stdc++.h>
using namespace std;
int m,n;
const int maxn=800001,inf=INT_MAX;
int lvl[maxn],tot=2,head[maxn],cur[maxn],s,t;
struct edge{
int u,v,w,nxt;
}ed[maxn];
void adde(int u,int v,int w){
ed[tot]={u,v,w,head[u]};
head[u]=tot;
tot++;
}
bool bfs(){
queue<int> q;
for(int i=0;i<maxn;i++)lvl[i]=-1;
lvl[s]=0;
q.push(s);
while(q.size()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=ed[i].nxt){
int v=ed[i].v,flow=ed[i].w;
if(lvl[v]==-1&&flow){
lvl[v]=lvl[u]+1;
q.push(v);
}
}
}
return lvl[t]!=-1;
}
int dfs(int u,int cap){
if(u==t)return cap;
int flow=0;
for(int i=cur[u];i&∩i=ed[i].nxt){
cur[u]=i;
int v=ed[i].v,fl=ed[i].w;
if(lvl[v]==lvl[u]+1){
int use=dfs(v,min(cap,fl));
if(use>0){
cap-=use;
flow+=use;
ed[i].w-=use;
ed[i^1].w+=use;
}
}
}
return flow;
}
void dinic(){
while(bfs()){
memcpy(cur,head,sizeof(head));
int tmp=dfs(s,inf);
}
}
int E[maxn],I[maxn];
signed main(){
//有m个实验，每个实验只可以进行一次，但会获得相应的奖金。
//有n个仪器，每个实验都需要一定的仪器，每个仪器可以运用于多个实验，但需要一定的价值。
//问奖金与代价的差的最大值是多少？
ios::sync_with_stdio(0);cin.tie(0);
int T;
cin>>T;
while(T--){
cin>>n>>m;
string str;
s=0,t=n+m+1;
tot=2;
memset(head,0,sizeof(head));
for(int i=0;i<maxn;i++)ed[i]={0,0,0,0};
memset(E,0,sizeof(E));
memset(I,0,sizeof(I));
for(int i=1;i<=n;i++){
int p;
cin>>p;
adde(i+m,t,p);
adde(t,i+m,0);
I[i+m]=p;
}
for(int i=1;i<=m;i++){
int idA,idB,p;
cin>>idA>>idB;
adde(i,idA+m,inf);
adde(idA+m,i,0);
adde(i,idB+m,inf);
adde(idB+m,i,0);
cin>>p;//p 为赞助商同意支付该实验的费用
E[i]=p;
adde(s,i,p);
adde(i,s,0);
}
//最小割选择点
dinic();
int g=0,k=0;
for(int i=head[s];i;i=ed[i].nxt){
if(lvl[ed[i].v]!=-1){
g+=E[ed[i].v];
}
}
for(int i=head[t];i;i=ed[i].nxt){
if(lvl[ed[i].v]!=-1){
k+=I[ed[i].v];
}
}
cout<<g-k<<endl;
}
return 0;
}
```
:::
### [P4177 [CEOI 2008] order](https://www.luogu.com.cn/problem/P4177)
这道题新增了租借功能，可以对于单个工作，租借机器。
怎么处理呢？
考虑在之前的建模上进行修改，将工作与机器之间的连边的边权从 $\infty$ 改为 $b_{ij}$。
为什么这样是对的？
想一下之前为什么要设为 $\infty$：是为了让最小割无法选择这条边割掉，来保证**选了某一个工作就必须选择所有对应的机器**。
但现在不是了。选择了某一个工作，不一定要选择所有对应的机器，还可以花钱 $b_{ij}$ 租机器。
~~不要在意注释。~~
:::info[code]
```cpp
#include<bits/stdc++.h>
using namespace std;
int m,n;
const int maxn=3000001,inf=INT_MAX;
int lvl[maxn],tot=2,head[maxn],cur[maxn],s,t;
struct edge{
int u,v,w,nxt;
}ed[maxn];
void adde(int u,int v,int w){
ed[tot]={u,v,w,head[u]};
head[u]=tot;
tot++;
}
bool bfs(){
queue<int> q;
for(int i=0;i<maxn;i++)lvl[i]=-1;
lvl[s]=0;
q.push(s);
while(q.size()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=ed[i].nxt){
int v=ed[i].v,flow=ed[i].w;
if(lvl[v]==-1&&flow){
lvl[v]=lvl[u]+1;
q.push(v);
}
}
}
return lvl[t]!=-1;
}
int dfs(int u,int cap){
if(u==t)return cap;
int flow=0;
for(int i=cur[u];i&∩i=ed[i].nxt){
cur[u]=i;
int v=ed[i].v,fl=ed[i].w;
if(lvl[v]==lvl[u]+1){
int use=dfs(v,min(cap,fl));
if(use>0){
cap-=use;
flow+=use;
ed[i].w-=use;
ed[i^1].w+=use;
}
}
}
return flow;
}
int dinic(){
int ans=0;
while(bfs()){
memcpy(cur,head,sizeof(head));
ans+=dfs(s,inf);
}
return ans;
}
int E[maxn],I[maxn];
signed main(){
//有m个实验，每个实验只可以进行一次，但会获得相应的奖金。
//有n个仪器，每个实验都需要一定的仪器，每个仪器可以运用于多个实验，但需要一定的价值。
//问奖金与代价的差的最大值是多少？
ios::sync_with_stdio(0);cin.tie(0);
cin>>n>>m;
long long sum=0;
s=0,t=n+m+1;
for(int i=1;i<=n;i++){
int x,p;
cin>>x>>p;
sum+=x;
adde(s,i,x);
adde(i,s,0);
for(int j=1;j<=p;j++){
int a,b;
cin>>a>>b;
adde(i,a+n,b);
adde(a+n,i,0);
}
}
for(int i=1;i<=m;i++){
int y;
cin>>y;
adde(i+n,t,y);
adde(t,i+n,0);
}
cout<<sum-dinic();
return 0;
}
// 喵喵喵！
```
:::
### [P3980 [NOI2008] 志愿者招募](https://www.luogu.com.cn/problem/P3980)
首先建立超级源点和汇点，提供流量。
注：本题中使用 $\inf$ 而非 $\infty$，因为这两者不同。
对于每一天，将 $i,i+1$ 连接容量 $\inf-a_i$，表示需求，每一种志愿者连接 $\{s_i,t_i+1,\inf,c_i\}$。
为什么要这样做？
我们发现，志愿者连的边其实就是不够的，还需要补充的人数。
那为什么是 $s_i\to t_i+1$ 呢？
这表示每一种志愿者管辖的区间。在 $s_i$ 天，一些志愿者沿着边流走，表示使用了这些志愿者，到了第 $t_i+1$ 天，他们流回来了，表示这些志愿者的服务结束了。
**事实上，如果主轴流量为 $f$，表示当前的需求为 $\inf -f$。志愿者流走，表示志愿者进行了工作，需求减少了。**
:::info[code]
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=500100,inf=INT_MAX;
int n,m,s,t,head[maxn],tot=2,dis[maxn],cur[maxn];//inqueue
struct edge{
int u,v,w,c,nxt;
}ed[maxn];
bool inq[maxn],vis[maxn];
queue<int> q;
void adde(int u,int v,int w,int c){
ed[tot]={u,v,w,c,head[u]};
head[u]=tot;
tot++;
}
bool spfa(){
for(int i=0;i<maxn;i++)dis[i]=inf;
dis[s]=0;
inq[s]=1;
q.push(s);
while(q.size()){
int u=q.front();
q.pop();
inq[u]=0;
for(int i=head[u];i;i=ed[i].nxt){
int v=ed[i].v,c=ed[i].c,flow=ed[i].w;
if(dis[v]>dis[u]+c&&flow){
dis[v]=dis[u]+c;
if(!inq[v])q.push(v);
inq[v]=1;
}
}
}
return dis[t]!=inf;
}
int dfs(int u,int cap){
int flow=0;
if(u==t)return cap;
vis[u]=1;
for(int i=cur[u];i&∩i=ed[i].nxt){
cur[u]=i;
int v=ed[i].v,c=ed[i].c,fl=ed[i].w;
if(dis[v]==dis[u]+c&&fl&&!vis[v]){
int use=dfs(v,min(cap,fl));
if(use>0){
ed[i].w-=use;
ed[i^1].w+=use;
flow+=use;
cap-=use;
}
}
}
vis[u]=0;
return flow;
}
pair<int,int> dinic(){
int flow=0,cost=0;
while(spfa()){
memcpy(cur,head,sizeof(head));
int fl=dfs(s,inf);
flow+=fl;
cost+=fl*dis[t];
}
return {flow,cost};
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);
cin>>n>>m;
s=0,t=n+2;
adde(s,1,inf,0);
adde(1,s,0,0);
adde(n+1,t,inf,0);
adde(t,n+1,0,0);
for(int i=1;i<=n;i++){
int ai;
cin>>ai;
adde(i,i+1,inf-ai,0);
adde(i+1,i,0,0);
}
for(int i=1;i<=m;i++){
int l,r,c;
cin>>l>>r>>c;
adde(l,r+1,inf,c);
adde(r+1,l,0,-c);
}
cout<<dinic().second;
return 0;
}
```
:::
### [P2457 [SDOI2006] 仓库管理员的烦恼](https://www.luogu.com.cn/problem/P2457)
考虑如果这个仓库 $i$ 含有 $a_{i,j}$ 个 $j$ 物品，那么这个仓库全放 $j$ 的代价就是 $sum_j-a_{i,j}$。
考虑建立二分图，左边为物品，右边为仓库，物品 $j$ 与仓库 $i$ 之间连边，容量为 $1$，费用为 $sum_j-a_{i,j}$。（实际上，只要容量 $>1$ 就行了）
然后就是二分图最小权最大匹配了。
:::info[为什么是最大匹配]
因为要将每一个仓库装满，并且：
- 每一种物品必须在同一个仓库中。
- 每一个仓库中只有一种物品。
:::
:::info[code]
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=500100,inf=INT_MAX;
int n,m,s,t,head[maxn],tot=2,dis[maxn],cur[maxn];//inqueue
struct edge{
int u,v,w,c,nxt;
}ed[maxn];
bool inq[maxn],vis[maxn];
queue<int> q;
void adde(int u,int v,int w,int c){
ed[tot]={u,v,w,c,head[u]};
head[u]=tot;
tot++;
}
bool spfa(){
for(int i=0;i<maxn;i++)dis[i]=inf;
dis[s]=0;
inq[s]=1;
q.push(s);
while(q.size()){
int u=q.front();
q.pop();
inq[u]=0;
for(int i=head[u];i;i=ed[i].nxt){
int v=ed[i].v,c=ed[i].c,flow=ed[i].w;
if(dis[v]>dis[u]+c&&flow){
dis[v]=dis[u]+c;
if(!inq[v])q.push(v);
inq[v]=1;
}
}
}
return dis[t]!=inf;
}
int dfs(int u,int cap){
int flow=0;
if(u==t)return cap;
vis[u]=1;
for(int i=cur[u];i&∩i=ed[i].nxt){
cur[u]=i;
int v=ed[i].v,c=ed[i].c,fl=ed[i].w;
if(dis[v]==dis[u]+c&&fl&&!vis[v]){
int use=dfs(v,min(cap,fl));
if(use>0){
ed[i].w-=use;
ed[i^1].w+=use;
flow+=use;
cap-=use;
}
}
}
vis[u]=0;
return flow;
}
pair<int,int> dinic(){
int flow=0,cost=0;
while(spfa()){
memcpy(cur,head,sizeof(head));
int fl=dfs(s,inf);
flow+=fl;
cost+=fl*dis[t];
}
return {flow,cost};
}
int pt[155][155],sum[155];
signed main(){
ios::sync_with_stdio(0);cin.tie(0);
int n;
cin>>n;
s=0,t=n*2+2;
for(int i=1;i<=n;i++){//仓库
for(int j=1;j<=n;j++){//货物
cin>>pt[i][j];
sum[j]+=pt[i][j];
}
}
for(int i=1;i<=n;i++){
adde(s,i,1,0);
adde(i,s,0,0);
adde(i+n,t,1,0);
adde(t,i+n,0,0);
}
for(int i=1;i<=n;i++){//货物
for(int j=1;j<=n;j++){//仓库
int val=pt[j][i];
adde(i,j+n,1,sum[i]-pt[j][i]);
adde(j+n,i,0,-sum[i]+pt[j][i]);
}
}
cout<<dinic().second;
return 0;
}
```
:::
## 最小割树
最小割树是一种**求解两点之间最小割的算法**。
具体地，我们使用分治法。
我们先在原图 $G$ 中**任意选择两点** $u,v$，得到他们的最小割。
那么我们就得到了两个**点集** $U,V$。
我们再在 $U$ 中选择 $u',v'$，继续跑最小割，再继续分。
这样为什么是对的呢？
设 $C(u,v)$ 表示 $u,v$ 之间的最小割，$F(u,v)$ 表示 $u,v$ 之间的最大流。
我们知道，$\forall u,v\in G,F(u,v)=C(u,v)$。
:::info[引理 1：$\forall x\in U,y\in V,C(x,y)\le C(u,v)$]
反证法，设 $C(x,y)>C(u,v)$，那么 $F(x,y)>F(u,v)$，显然不成立。
:::
我们构造一棵树 $T$，将每次选择的 $u,v$ 连接，边权为 $C(u,v)$。
:::info[为什么能构成树]
首先考虑边数。递归树是一棵二叉树，叶节点（$|S_{now}|=1$）的个数为 $n$，那么非叶节点个数为 $n-1$。
由于只有在 $|S_{now}|>1$ 时分割，所以分割次数为 $n-1$，对应边数为 $n-1$。
连通性显然。
:::
那么 $C(u,v)$ 就转化为 $u,v$ 在 $T$ 上的路径边权最小值。
:::info[证明]
割掉 $w_{\min}$ 显然 $u,v$ 分开，所以这个一个割，由于最小割是割中最小的，所以 $c\le w_{\min}$。
考虑存在一条树边 $(a,b)$，且这条边被割开，即 $a\in U,b\in V$。
由引理 1，如果树边 $(a,b)$ 边权为 $w$，那么 $w\le c$。
所以 $w_{\min}\le w\le c$。
$w_{\min}\le c\le w_{\min},w_{\min}=c$。
:::
使用树剖解决。
~~怎么会有【数据删除】写树剖啊！~~ $n$ 这么小，其实暴力可行。
:::warning[树剖的注意]{open}
我们需要使用边权转点权。
但是，记得在查询 $u,v$ 时，不要计算 $\operatorname{lca}(u,v)$ 的边权！
:::
### [P4897 【模板】最小割树（Gomory-Hu Tree）](https://www.luogu.com.cn/problem/P4897)
:::info[code]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N=510,M=6514,inf=INT_MAX;
int head[N],cur[N],lvl[N],tot=2;
struct edge{
int u,v,w,nxt;
}ed[M],ed2[M];
void adde(int u,int v,int w){
ed[tot]={u,v,w,head[u]};
head[u]=tot;
tot++;
}
bool bfs(int s,int t){
for(int i=0;i<N;i++)lvl[i]=-1;
lvl[s]=0;
queue<int> q;
q.push(s);
while(q.size()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=ed[i].nxt){
int v=ed[i].v,flow=ed[i].w;
if(flow&&lvl[v]==-1){
lvl[v]=lvl[u]+1;
q.push(v);
}
}
}
return lvl[t]!=-1;
}
int dfs(int t,int u,int cap){
if(u==t)return cap;
int flow=0;
for(int i=cur[u];i&∩i=ed[i].nxt){
cur[u]=i;
int v=ed[i].v,fl=ed[i].w;
if(lvl[v]==lvl[u]+1&&fl){
int use=dfs(t,v,min(cap,fl));
if(use>0){
ed[i].w-=use;
ed[i^1].w+=use;
flow+=use;
cap-=use;
}
}
}
return flow;
}
int dinic(int s,int t){
int flow=0;
while(bfs(s,t)){
memcpy(cur,head,sizeof(head));
flow+=dfs(t,s,inf);
}
return flow;
}
int n,m;
struct TreeE{
int v,w;
};
vector<TreeE> T[N];
bitset<N> ins;
vector<int> pihua;
int dep[N],top[N],fa[N],siz[N],heavy[N],dfn[N],ord=0,td[N],val[N];
void div(vector<int> S){//分治
if(S.size()<=1)return;
int s=S[0],t=S[1];
for(int i=0;i<M;i++)ed[i]=ed2[i];
int cut=dinic(s,t);
T[s].push_back({t,cut});
T[t].push_back({s,cut});
vector<int> lf,rg;
for(auto i:S){
if(lvl[i]!=-1)lf.push_back(i);
else rg.push_back(i);
}
div(lf);
div(rg);
}
struct segment{
int l,r,min;
}t[N*4];
#define ls id<<1
#define rs id<<1|1
void up(int id){
t[id].min=min(t[ls].min,t[rs].min);
}
void build(int id,int l,int r){
t[id]={l,r,inf};
if(l==r){
t[id].min=val[td[l]];
return;
}
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
up(id);
}
int query(int id,int l,int r){
if(t[id].l>r||l>t[id].r)return inf;
if(l<=t[id].l&&t[id].r<=r)return t[id].min;
return min(query(ls,l,r),query(rs,l,r));
}
void dfs1(int u,int f){
dep[u]=dep[f]+1;
fa[u]=f;
siz[u]=1;
int miz=0;
for(auto [v,tmp]:T[u]){
if(v!=f){
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>miz)heavy[u]=v,miz=siz[v];
}
}
}
void dfs2(int u,int tp){
top[u]=tp;
dfn[u]=++ord;
td[ord]=u;
if(!heavy[u])return;
dfs2(heavy[u],tp);
for(auto [v,tmp]:T[u]){
if(v==fa[u])continue;
if(v!=heavy[u])dfs2(v,v);
}
}
void tov(int u){
for(auto [v,vv]:T[u]){
if(v!=fa[u]){
val[v]=vv;
tov(v);
}
}
}
int get(int u,int v){
int ans=inf;
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
ans=min(ans,query(1,dfn[top[u]],dfn[u]));
u=fa[top[u]];
}
if(dep[u]>dep[v])swap(u,v);
if(u!=v)ans=min(ans,query(1,dfn[u]+1,dfn[v]));
return ans;
}
int root=1;
signed main(){
ios::sync_with_stdio(0);cin.tie(0);
top[root]=root;
cin>>n>>m;
n++;
while(m--){
int u,v,w;
cin>>u>>v>>w;
u++,v++;
adde(u,v,w);
adde(v,u,0);
adde(v,u,w);
adde(u,v,0);
}
for(int i=0;i<M;i++)ed2[i]=ed[i];
for(int i=1;i<=n;i++)pihua.push_back(i);//点集
div(pihua);
for(int i=0;i<N;i++)val[i]=inf;
dfs1(root,root);
dfs2(root,1);
tov(root);
build(1,1,n);
int q;
cin>>q;
while(q--){
int u,v;
cin>>u>>v;
u++,v++;
cout<<get(u,v)<<endl;
}
return 0;
}
```
:::
## 上下界网络流
这种网络流不仅有最高流量，还有最低流量限制，也就是边的流量满足 $l(u,v)\le flow(u,v)\le r(u,v)$。
## 无源汇上下界可行流
设 $H(u\to v)$ 表示有 $u\to v$ 这条边。
其实就是：请设计边权，满足下列条件：
1. $l(u,v)\le w(u,v)\le r(u,v)$。
2. $\forall u\in V,\sum\limits_{\{x\in V|H(x\to u)\}}w(x,u)=\sum\limits_{\{x\in V|H(u\to x)\}}w(u,x)$。
我们建立下界网络 $G_{\text{low}}$。
我们从[阴阳](https://cn.puzzle-yin-yang.com/)中联想到可以用**调整大法**。直接假设现在网络已经流了下界的流量 $l(u,v)$。
现在，这个流函数 $f(u)=\sum\limits_{\{x\in V|H(x\to u)\}}w(x,u)-\sum\limits_{\{x\in V|H(u\to x)\}}w(u,x)$ 不一定为 $0$，开始在 $G_{\text{low}}$ 调整。
- 如果 $f(u)=0$，不用调整。
- 如果 $f(u)<0$，将超级源点 $s$ 和 $u$ 连接边 $|f(u)|$，表示提供流。
- 如果 $f(u)>0$，将 $u$ 和超级汇点 $t$ 连接边 $|f(u)|$，表示提供流。
- 跑最大流，如果 $s$ 连接的所有边全部流满了，那么说明有解，每一条边的流量是 $l_i+use_i$，也就是下界与 $G_{\text{low}}$ 最大流流过的流量之和。
```cpp
for(int i=1;i<=m;i++){
cout<<R[i]-ed[i<<1].w<<endl;//就是L[i]+ed[i<<1|1].w
}
```
上面的代码中，`ed[i<<1].w` 就是剩下的流量，`ed[i<<1|1].w` 就是流过的流量，反正怎么写都是一样的。
:::info[为什么不用判断和 $t$ 连接的边是否流满]{open}
流量守恒，这样多余了，没有必要。
:::
:::info[为什么要跑最大流]{open}
我们的目的是尽可能让网络平衡，所以要让最大流来流满新建的差值边。
:::
:::info[code]
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1205,M=25005,inf=2147483647;
int n,m,s,t;
int lvl[N];//层数
struct edge{
int u,v,w;
int nxt;
}ed[M*2];
int head[N],cur[N],cnt=2,infl[N],outfl[N],R[M];
void adde(int u,int v,int w){
ed[cnt].u=u;
ed[cnt].v=v;
ed[cnt].w=w;
ed[cnt].nxt=head[u];
head[u]=cnt;
cnt++;
}
bool bfs(){
queue<int> q;
for(int i=0;i<=n+1;i++)lvl[i]=-1;
lvl[s]=0;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=ed[i].nxt){
if(lvl[ed[i].v]==-1&&ed[i].w>0){
lvl[ed[i].v]=lvl[u]+1;
q.push(ed[i].v);
if(ed[i].v==t)return 1;
}
}
}
return(lvl[t]!=-1);
}
int dfs(int u,int cap){//cap:容量
int flow=0;//跑过的流
if(u==t)return cap;
for(int i=cur[u];i&∩i=ed[i].nxt){
cur[u]=i;
int v=ed[i].v,w=ed[i].w;
if(w&&lvl[v]==lvl[u]+1){
int use=dfs(v,min(cap,w));
if(use==0)lvl[v]=-1;
if(use>0){
ed[i].w-=use;
ed[i^1].w+=use;
cap-=use;
flow+=use;
}
}
}
return flow;
}
int dinic(){
int ans=0;
while(bfs()){
cerr<<"ok";
memcpy(cur,head,sizeof(head));
ans+=dfs(s,inf);
}
return ans;
}
signed main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v,l,r;
cin>>u>>v>>l>>r;
adde(u,v,r-l);
adde(v,u,0);
outfl[u]+=l;
infl[v]+=l;
R[i]=r;
}
s=0,t=n+1;
bool pd=1;
for(int i=1;i<=n;i++){
if(infl[i]>outfl[i]){//连接s->i
adde(s,i,infl[i]-outfl[i]);
adde(i,s,0);
}
else if(infl[i]<outfl[i]){
adde(i,t,outfl[i]-infl[i]);
adde(t,i,0);
}
}
int ans=dinic();
for(int i=head[s];i&&pd;i=ed[i].nxt){
if(ed[i].w)pd=0;
}
if(pd){
cout<<"Yes\n";
for(int i=1;i<=m;i++){
cout<<R[i]-ed[i<<1].w<<endl;
}
}
else cout<<"No";
return 0;
}
```
:::
## 有源汇上下界可行流
我们仍然遵循无源汇上下界可行流的做法，将**真实汇点 $T$ 与真实源点 $S$ 连接一条上界为 $\infty$，下界为 $0$ 的引流边**，将 $T$ 的流量引到 $S$。
引流边的流量就是可行流大小，因为这对应着 $T$ 的流出。
:::info[为什么要引流]{open}
比较无源汇，这里要求变了。
设 $V'=V\setminus\{S,T\}$。
1. $l(u,v)\le w(u,v)\le r(u,v)$。
2. $\forall u\in V',\sum\limits_{\{x\in V|H(x\to u)\}}w(x,u)=\sum\limits_{\{x\in V|H(u\to x)\}}w(u,x)$。
3. $\sum\limits_{\{x\in V|H(x\to T)\}}w(x,T)=\sum\limits_{\{x\in V|H(S\to x)\}}w(S,x)
说人话就是：S 点有净流出，T 点有净流入，且这两个相等。
我们要把这个网络变得循环，连一条边即可。
:::
有源汇上下界最大流
跑完可行流之后，删掉新建的 T\to S 的边，跑最大流。
:::info[为什么并不是直接在增量网络上跑最大流，而是在跑完可行流后的残量网络上再去跑最大流。]{open}
我们还是使用调整的方式思考，对于这个可行流，我们直接在这个网络上增广，才能保证至少可行。
:::
:::info[code]
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1205,M=25005,inf=2147483647;
int n,m,s,t,S,T;
int lvl[N];//层数
struct edge{
int u,v,w;
int nxt;
}ed[M*2];
int head[N],cur[N],cnt=2,infl[N],outfl[N],R[M];
void adde(int u,int v,int w){
ed[cnt].u=u;
ed[cnt].v=v;
ed[cnt].w=w;
ed[cnt].nxt=head[u];
head[u]=cnt;
cnt++;
}
bool bfs(){
queue<int> q;
for(int i=0;i<=n+1;i++)lvl[i]=-1;
lvl[s]=0;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=ed[i].nxt){
if(lvl[ed[i].v]==-1&&ed[i].w>0){
lvl[ed[i].v]=lvl[u]+1;
q.push(ed[i].v);
if(ed[i].v==t)return 1;
}
}
}
return(lvl[t]!=-1);
}
int dfs(int u,int cap){//cap:容量
int flow=0;//跑过的流
if(u==t)return cap;
for(int i=cur[u];i&∩i=ed[i].nxt){
cur[u]=i;
int v=ed[i].v,w=ed[i].w;
if(w&&lvl[v]==lvl[u]+1){
int use=dfs(v,min(cap,w));
if(use==0)lvl[v]=-1;
if(use>0){
ed[i].w-=use;
ed[i^1].w+=use;
cap-=use;
flow+=use;
}
}
}
return flow;
}
int dinic(){
int ans=0;
while(bfs()){
cerr<<"ok";
memcpy(cur,head,sizeof(head));
ans+=dfs(s,inf);
}
return ans;
}
signed main(){
cin>>n>>m>>S>>T;
for(int i=1;i<=m;i++){
int u,v,l,r;
cin>>u>>v>>l>>r;
adde(u,v,r-l);
adde(v,u,0);
outfl[u]+=l;
infl[v]+=l;
R[i]=r;
}
s=0,t=n+1;
bool pd=1;
for(int i=1;i<=n;i++){
if(infl[i]>outfl[i]){//连接s->i
adde(s,i,infl[i]-outfl[i]);
adde(i,s,0);
}
else if(infl[i]<outfl[i]){
adde(i,t,outfl[i]-infl[i]);
adde(t,i,0);
}
}
adde(T,S,inf);
int sp=cnt;
adde(S,T,0);
dinic();
for(int i=head[s];i&&pd;i=ed[i].nxt){
if(ed[i].w)pd=0;
}
int able=ed[sp].w;//可行流
if(!pd){
cout<<"N";
return 0;
}
ed[sp].w=ed[sp^1].w=0;//删边
s=S,t=T;
cout<<able+dinic();
return 0;
}
:::
有源汇上下界最小流
我们还是使用调整的方式思考，对于这个可行流，我们直接在这个网络上退流，才能保证至少可行。
因为是退流，所以要反着跑，从 T 到 S。
最后答案就是可行流减去退的流（反着的最大流）。
:::info[code]
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1205,M=25005,inf=2147483647;
int n,m,s,t,S,T;
int lvl[N];//层数
struct edge{
int u,v,w;
int nxt;
}ed[M*2];
int head[N],cur[N],cnt=2,infl[N],outfl[N],R[M];
void adde(int u,int v,int w){
ed[cnt].u=u;
ed[cnt].v=v;
ed[cnt].w=w;
ed[cnt].nxt=head[u];
head[u]=cnt;
cnt++;
}
bool bfs(){
queue<int> q;
for(int i=0;i<=n+1;i++)lvl[i]=-1;
lvl[s]=0;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=ed[i].nxt){
if(lvl[ed[i].v]==-1&&ed[i].w>0){
lvl[ed[i].v]=lvl[u]+1;
q.push(ed[i].v);
if(ed[i].v==t)return 1;
}
}
}
return(lvl[t]!=-1);
}
int dfs(int u,int cap){//cap:容量
int flow=0;//跑过的流
if(u==t)return cap;
for(int i=cur[u];i&∩i=ed[i].nxt){
cur[u]=i;
int v=ed[i].v,w=ed[i].w;
if(w&&lvl[v]==lvl[u]+1){
int use=dfs(v,min(cap,w));
if(use==0)lvl[v]=-1;
if(use>0){
ed[i].w-=use;
ed[i^1].w+=use;
cap-=use;
flow+=use;
}
}
}
return flow;
}
int dinic(){
int ans=0;
while(bfs()){
cerr<<"ok";
memcpy(cur,head,sizeof(head));
ans+=dfs(s,inf);
}
return ans;
}
signed main(){
cin>>n>>m>>S>>T;
for(int i=1;i<=m;i++){
int u,v,l,r;
cin>>u>>v>>l>>r;
adde(u,v,r-l);
adde(v,u,0);
outfl[u]+=l;
infl[v]+=l;
R[i]=r;
}
s=0,t=n+1;
bool pd=1;
for(int i=1;i<=n;i++){
if(infl[i]>outfl[i]){//连接s->i
adde(s,i,infl[i]-outfl[i]);
adde(i,s,0);
}
else if(infl[i]<outfl[i]){
adde(i,t,outfl[i]-infl[i]);
adde(t,i,0);
}
}
adde(T,S,inf);
int sp=cnt;
adde(S,T,0);
dinic();
for(int i=head[s];i&&pd;i=ed[i].nxt){
if(ed[i].w)pd=0;
}
int able=ed[sp].w;//可行流
if(!pd){
cout<<"N";
return 0;
}
ed[sp].w=ed[sp^1].w=0;//删边
s=T,t=S;
cout<<able-dinic();
return 0;
}
:::
最小割树（Gomory-Hu Tree）
最小割树是一种求解两点之间最小割的算法。
具体地，我们使用分治法。
我们先在原图 G 中任意选择两点 u,v，得到他们的最小割。
那么我们就得到了两个点集 U,V。
我们再在 U 中选择 u',v'，继续跑最小割，再继续分……
这样为什么是对的呢？
设 C(u,v) 表示 u,v 之间的最小割，F(u,v) 表示 u,v 之间的最大流。
我们知道，\forall u,v\in G,F(u,v)=C(u,v)。
:::info[引理 1：\forall x\in U,y\in V,C(x,y)\le C(u,v)]{open}
反证法，设 C(x,y)>C(u,v)，那么 F(x,y)>F(u,v)，显然不成立。
:::
我们构造一棵树 T，将每次选择的 u,v 连接，边权为 C(u,v)。
:::info[为什么能构成树]{open}
首先考虑边数。递归树是一棵二叉树，叶节点（|S_{now}|=1）的个数为 n，那么非叶节点个数为 n-1。
由于只有在 |S_{now}|>1 时分割，所以分割次数为 n-1，对应边数为 n-1。
连通性显然。
:::
那么 C(u,v) 就转化为 u,v 在 T 上的路径边权最小值。
:::info[证明]{open}
割掉 w_{\min} 显然 u,v 分开，所以这个一个割，由于最小割是割中最小的，所以 c\le w_{\min}。
考虑存在一条树边 (a,b)，且这条边被割开，即 a\in U,b\in V。
由引理 1，如果树边 (a,b) 边权为 w，那么 w\le c。
所以 w_{\min}\le w\le c。
:::
使用树剖解决。
:::warning[树剖的注意]
我们需要使用边权转点权。
但是，记得在查询 $u,v$ 时，不要计算 $\operatorname{lca}(u,v)$ 的边权！
:::
## 玄学时间复杂度
### [P4480 [BJWC2018] 餐巾计划问题](https://www.luogu.com.cn/problem/P4480)
本题和网络流24题中的餐巾计划**为**重题。
考虑**分类**加边，将容量为 $\infty$ 的边放到最后加即可。
$O(n^3)$ 过 $n=200000$，~~暴力踩标算~~这个还是算了。
那个 spfa 的优化，没啥用。
:::info[code]
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=12200001,inf=INT_MAX;
int n,m,s,t,head[maxn],tot=2,dis[maxn],cur[maxn],a,b,p;//inqueue
struct edge{
int u,v,w,c,nxt;
}ed[maxn];
bool inq[maxn],vis[maxn];
void adde(int u,int v,int w,int c){
ed[tot]={u,v,w,c,head[u]};
head[u]=tot;
tot++;
}
deque<int> q;
int sum=0;
bool spfa(){
for(int i=1;i<min(n*3+3,maxn);i++)dis[i]=inf;
dis[s]=0;
sum+=dis[s];
int num=1;
q.push_back(s);
while(!q.empty()){
int u=q.front();
while(dis[u]*num>sum){
q.pop_front();
q.push_back(u);
u=q.front();
}
q.pop_front();
sum-=dis[u];
num--;
inq[u]=0;
for(int i=head[u];i;i=ed[i].nxt){
int v=ed[i].v,c=ed[i].c;
if(dis[v]>dis[u]+c&&ed[i].w){
dis[v]=dis[u]+c;
if(!q.empty()&&dis[v]>dis[q.front()])q.push_back(v);
else q.push_front(v);
sum+=dis[v];
num++;
inq[v]=1;
}
}
}
return dis[t]!=inf;
}
int dfs(int u,int cap){
int flow=0;
if(u==t)return cap;
vis[u]=1;
for(int i=cur[u];i&∩i=ed[i].nxt){
cur[u]=i;
int v=ed[i].v,c=ed[i].c,fl=ed[i].w;
if(dis[v]==dis[u]+c&&fl&&!vis[v]){
int use=dfs(v,min(cap,fl));
if(use>0){
ed[i].w-=use;
ed[i^1].w+=use;
flow+=use;
cap-=use;
}
}
}
vis[u]=0;
return flow;
}
pair<int,int> dinic(){
int flow=0,cost=0;
while(spfa()){
for(int i=0;i<min(n*3+3,maxn);i++)cur[i]=head[i];
int fl=dfs(s,inf);
flow+=fl;
cost+=fl*dis[t];
}
return {flow,cost};
}
int nd[maxn],idx=0;
signed main(){
int q,k,d,f;
ios::sync_with_stdio(0);cin.tie(0);
cin>>n>>m>>d>>f>>k>>p;
for(int i=1;i<=n;++i)cin>>nd[i];
s=0;t=n*2+1;
for(int i=1;i<=n;i++){//i+n是早上，i是晚上
adde(s,i,nd[i],0);
adde(i,s,0,0);
adde(i+n,t,nd[i],0);
adde(t,i+n,0,0);
}
for(int i=1;i<=n;i++){
if(i+m<=n)adde(i,i+n+m,inf,f);
if(i+m<=n)adde(i+n+m,i,0,-f);
if(i+d<=n)adde(i,i+n+d,inf,k);
if(i+d<=n)adde(i+n+d,i,0,-k);
if(i+1<=n)adde(i,i+1,inf,0);
if(i+1<=n)adde(i+1,i,0,0);
adde(s,i+n,inf,p);
adde(i+n,s,0,-p);
}
cout<<dinic().second;
return 0;
}
```
:::
### 几个玄学优化
### Part A-1：用费用流跑最大流
费用设为 $\inf/w$，算是估价？
得分：$\small\textbf{\textsf{\color{#F39C11}{52}}}$。
:::info[code]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int maxn=240001,inf=1e18;
int n,m,s,t,head[maxn],tot=2,dis[maxn],cur[maxn];//inqueue
struct edge{
int u,v,w,c,nxt;
}ed[maxn];
bool inq[maxn],vis[maxn];
__inline void adde(int u,int v,int w,int c){
ed[tot]={u,v,w,c,head[u]};
head[u]=tot;
tot++;
}
int sum=0;
deque<int> q;
__inline bool spfa(){
for(int i=1;i<=n;i++)dis[i]=inf;
dis[s]=0;
sum+=dis[s];
int num=1;
q.push_back(s);
while(!q.empty()){
int u=q.front();
while(dis[u]*num>sum){
q.pop_front();
q.push_back(u);
u=q.front();
}
q.pop_front();
sum-=dis[u];
num--;
inq[u]=0;
for(int i=head[u];i;i=ed[i].nxt){
int v=ed[i].v,c=ed[i].c;
if(dis[v]>dis[u]+c&&ed[i].w){
dis[v]=dis[u]+c;
if(!q.empty()&&dis[v]>dis[q.front()])q.push_back(v);
else q.push_front(v);
sum+=dis[v];
num++;
inq[v]=1;
}
}
}
return dis[t]!=inf;
}
int dfs(int u,int cap){
int flow=0;
if(u==t)return cap;
vis[u]=1;
for(int i=cur[u];i&∩i=ed[i].nxt){
cur[u]=i;
int v=ed[i].v,c=ed[i].c,fl=ed[i].w;
if(dis[v]==dis[u]+c&&fl&&!vis[v]){
int use=dfs(v,min(cap,fl));
if(use==0)dis[v]=inf;
if(use>0){
ed[i].w-=use;
ed[i^1].w+=use;
flow+=use;
cap-=use;
}
}
}
vis[u]=0;
return flow;
}
pair<int,int> dinic(){
int flow=0,cost=0;
while(spfa()){
for(int i=1;i<=n;++i)cur[i]=head[i];
int fl=dfs(s,inf);
flow+=fl;
cost+=fl*dis[t];
}
return {flow,cost};
}
#ifdef LINUX
#define putchar putchar_unlocked
#define getchar getchar_unlocked
#endif
inline int read(){
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=(x << 1) + (x << 3)+ch-48;ch=getchar();}
return x*f;
}
inline void write(int x){
if(x<0){putchar('-');x=-x;}
if(x>9)write(x/10);
putchar(x%10+'0');
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);
n=read(),m=read(),s=read(),t=read();
for(int i=1;i<=m;++i){
int u,v,w;
u=read(),v=read(),w=read();
adde(u,v,w,200000000000000/w);
adde(v,u,0,-200000000000000/w);
}
pair<int,int> ans=dinic();
write(ans.first);
return 0;
}
```
:::
### Part B-1：分段加边
跑 $\log w_{\max}$ 次最大流，每次只加入 $2^i\le w<2^{i+1}$ 的边。
记得去掉重边。
得分：$\small\textbf{\textsf{\color{#FADB14}{68}}}$。
:::info[code]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1205,M=121005,inf=1e18;
int n,m,s,t;
int lvl[N],wt[N][N];//层数
struct edge{
int u,v,w;
int nxt;
}ed[M*2];
int head[N],cnt=2;
inline void adde(int u,int v,int w){
ed[cnt]={u,v,w,head[u]};
head[u]=cnt;
cnt++;
}
inline bool bfs(){
queue<int> q;
for(int i=1;i<=n;i++)lvl[i]=-1;
lvl[s]=0;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=ed[i].nxt){
if(lvl[ed[i].v]==-1&&ed[i].w>0){
lvl[ed[i].v]=lvl[u]+1;
if(ed[i].v==t)return 1;
q.push(ed[i].v);
}
}
}
return(lvl[t]!=-1);
}
int cur[N];
int dfs(int u,int cap){//cap:容量
int flow=0;//跑过的流
if(u==t)return cap;
for(int i=cur[u];i&∩i=ed[i].nxt){
cur[u]=i;
int v=ed[i].v,w=ed[i].w;
if(w&&lvl[v]==lvl[u]+1){
int use=dfs(v,min(cap,w));
if(use==0)lvl[v]=-1;
if(use>0){
ed[i].w-=use;
ed[i^1].w+=use;
cap-=use;
flow+=use;
}
}
}
return flow;
}
inline int dinic(){
int ans=0;
while(bfs()){
for(int i=1;i<=n;i++)cur[i]=head[i];
ans+=dfs(s,inf);
}
return ans;
}
struct inp{
int u,v,w;
};
vector<inp> ve;
#ifdef __linux__
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#else
#define getchar _getchar_nolock
#define putchar _putchar_nolock
#endif
inline int read(){
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=(x << 1) + (x << 3)+ch-48;ch=getchar();}
return x*f;
}
inline void write(int x){
if(x<0){putchar('-');x=-x;}
if(x>9)write(x/10);
putchar(x%10+'0');
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
n=read(),m=read(),s=read(),t=read();
for(int i=1;i<=m;++i){
int u,v,w;
u=read(),v=read(),w=read();
ve.push_back({u,v,w});
wt[u][v]+=w;
}
int fl=0;
for(int bt=32;bt>=0;bt-=4){
int l=1ll<<bt,r=1ll<<(bt+4);
bool W=0;
for(int u=1;u<=n;u++){
for(int v=1;v<=n;v++){
if(l<=wt[u][v]&&wt[u][v]<r&&wt[u][v]){
adde(u,v,wt[u][v]);
adde(v,u,0);
wt[u][v]=0;
W=1;
}
}
}
if(W)fl+=dinic();
}
write(fl);
dinic();
return 0;
}
```
:::
### Part B-2：贪心初始流
先不加残余边跑一边（只修改残余边，不遍历），再加上残余边跑。
得分：$\small\textbf{\textsf{\color{#FADB14}{68}}}$。
:::info[code]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1205,M=121005,inf=1e18;
int n,m,s,t;
int lvl[N],wt[N][N];//层数
struct edge{
int u,v,w;
int nxt;
}ed[M*2];
int head[N],cnt=2,cur[N];
inline void adde(int u,int v,int w){
ed[cnt]={u,v,w,head[u]};
head[u]=cnt;
cnt++;
}
inline bool bfs(){
queue<int> q;
for(int i=1;i<=n;i++)lvl[i]=-1;
lvl[s]=0;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=ed[i].nxt){
if(lvl[ed[i].v]==-1&&ed[i].w>0){
lvl[ed[i].v]=lvl[u]+1;
if(ed[i].v==t)return 1;
q.push(ed[i].v);
}
}
}
return(lvl[t]!=-1);
}
inline bool gbfs(){
queue<int> q;
for(int i=1;i<=n;i++)lvl[i]=-1;
lvl[s]=0;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=ed[i].nxt){
if(i%2)continue;
if(lvl[ed[i].v]==-1&&ed[i].w>0){
lvl[ed[i].v]=lvl[u]+1;
if(ed[i].v==t)return 1;
q.push(ed[i].v);
}
}
}
return(lvl[t]!=-1);
}
int dfs(int u,int cap){//cap:容量
int flow=0;//跑过的流
if(u==t)return cap;
for(int i=cur[u];i&∩i=ed[i].nxt){
cur[u]=i;
int v=ed[i].v,w=ed[i].w;
if(w&&lvl[v]==lvl[u]+1){
int use=dfs(v,min(cap,w));
if(use==0)lvl[v]=-1;
if(use>0){
ed[i].w-=use;
ed[i^1].w+=use;
cap-=use;
flow+=use;
}
}
}
return flow;
}
int greed(int u,int cap){//贪心初始流
int flow=0;//跑过的流
if(u==t)return cap;
for(int i=cur[u];i&∩i=ed[i].nxt){
cur[u]=i;
if((i%2))continue;
int v=ed[i].v,w=ed[i].w;
if(w&&lvl[v]==lvl[u]+1){
int use=greed(v,min(cap,w));
if(use==0)lvl[v]=-1;
if(use>0){
ed[i].w-=use;
ed[i^1].w+=use;
cap-=use;
flow+=use;
}
}
}
return flow;
}
inline int dinic(){
int ans=0;
while(bfs()){
for(int i=1;i<=n;i++)cur[i]=head[i];
ans+=dfs(s,inf);
}
return ans;
}
inline int gflow(){
int ans=0;
while(gbfs()){
for(int i=1;i<=n;i++)cur[i]=head[i];
ans+=greed(s,inf);
}
return ans;
}
#ifdef __linux__
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#else
#define getchar _getchar_nolock
#define putchar _putchar_nolock
#endif
inline int read(){
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=(x << 1) + (x << 3)+ch-48;ch=getchar();}
return x*f;
}
inline void write(int x){
if(x<0){putchar('-');x=-x;}
if(x>9)write(x/10);
putchar(x%10+'0');
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
n=read(),m=read(),s=read(),t=read();
for(int i=1;i<=m;++i){
int u,v,w;
u=read(),v=read(),w=read();
wt[u][v]+=w;
}
int fl=0;
for(int bt=28;bt>=0;bt-=4){
int l=1ll<<bt,r=1ll<<(bt+4);
bool W=0;
for(int u=1;u<=n;++u){
for(int v=1;v<=n;++v){
if(v==u)continue;
if(l<=wt[u][v]&&wt[u][v]<r&&wt[u][v]){
adde(u,v,wt[u][v]);
adde(v,u,0);
wt[u][v]=0;
W=1;
}
}
}
if(W)fl+=gflow(),fl+=dinic();
}
write(fl);
return 0;
}
```
:::
### Part B-3：分类加边
分类加边，将 $u\to v(u<v)$ 和 $u\to v(u>v)$ 分开加。
得分：$\small\textbf{\textsf{\color{#52C41A}{84}}}$。
:::info[code]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1205,M=121005,inf=1e18;
int n,m,s,t;
int lvl[N],wt[N][N];//层数
struct edge{
int u,v,w;
int nxt;
}ed[M*2];
int head[N],cnt=2,cur[N];
inline void adde(int u,int v,int w){
ed[cnt]={u,v,w,head[u]};
head[u]=cnt;
cnt++;
}
inline bool bfs(){
queue<int> q;
for(int i=1;i<=n;i++)lvl[i]=-1;
lvl[s]=0;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=ed[i].nxt){
if(lvl[ed[i].v]==-1&&ed[i].w>0){
lvl[ed[i].v]=lvl[u]+1;
if(ed[i].v==t)return 1;
q.push(ed[i].v);
}
}
}
return(lvl[t]!=-1);
}
inline bool gbfs(){
queue<int> q;
for(int i=1;i<=n;i++)lvl[i]=-1;
lvl[s]=0;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=ed[i].nxt){
if(i%2)continue;
if(lvl[ed[i].v]==-1&&ed[i].w>0){
lvl[ed[i].v]=lvl[u]+1;
if(ed[i].v==t)return 1;
q.push(ed[i].v);
}
}
}
return(lvl[t]!=-1);
}
int dfs(int u,int cap){//cap:容量
int flow=0;//跑过的流
if(u==t)return cap;
for(int i=cur[u];i&∩i=ed[i].nxt){
cur[u]=i;
int v=ed[i].v,w=ed[i].w;
if(w&&lvl[v]==lvl[u]+1){
int use=dfs(v,min(cap,w));
if(use==0)lvl[v]=-1;
if(use>0){
ed[i].w-=use;
ed[i^1].w+=use;
cap-=use;
flow+=use;
}
}
}
return flow;
}
int greed(int u,int cap){//贪心初始流
int flow=0;//跑过的流
if(u==t)return cap;
for(int i=cur[u];i&∩i=ed[i].nxt){
cur[u]=i;
if((i%2))continue;
int v=ed[i].v,w=ed[i].w;
if(w&&lvl[v]==lvl[u]+1){
int use=greed(v,min(cap,w));
if(use==0)lvl[v]=-1;
if(use>0){
ed[i].w-=use;
ed[i^1].w+=use;
cap-=use;
flow+=use;
}
}
}
return flow;
}
inline int dinic(){
int ans=0;
while(bfs()){
for(int i=1;i<=n;i++)cur[i]=head[i];
ans+=dfs(s,inf);
}
return ans;
}
inline int gflow(){
int ans=0;
while(gbfs()){
for(int i=1;i<=n;i++)cur[i]=head[i];
ans+=greed(s,inf);
}
return ans;
}
#ifdef __linux__
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#else
#define getchar _getchar_nolock
#define putchar _putchar_nolock
#endif
inline int read(){
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=(x << 1) + (x << 3)+ch-48;ch=getchar();}
return x*f;
}
inline void write(int x){
if(x<0){putchar('-');x=-x;}
if(x>9)write(x/10);
putchar(x%10+'0');
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
n=read(),m=read(),s=read(),t=read();
for(int i=1;i<=m;++i){
int u,v,w;
u=read(),v=read(),w=read();
wt[u][v]+=w;
}
int fl=0;
for(int bt=28;bt>=0;bt-=4){
int l=1ll<<bt,r=1ll<<(bt+4);
bool W=0;
for(int u=1;u<=n;++u){
for(int v=1;v<u;++v){
if(l<=wt[u][v]&&wt[u][v]<r&&wt[u][v]){
adde(u,v,wt[u][v]);
adde(v,u,0);
wt[u][v]=0;
W=1;
}
}
}
// if(W)fl+=gflow(),fl+=dinic();
// W=0;
for(int u=1;u<=n;++u){
for(int v=u+1;v<=n;++v){
if(l<=wt[u][v]&&wt[u][v]<r&&wt[u][v]){
adde(u,v,wt[u][v]);
adde(v,u,0);
wt[u][v]=0;
W=1;
}
}
}
if(W)fl+=gflow(),fl+=dinic();
}
write(fl);
return 0;
}
```
:::
### Part B-4：双向边优化
在无向图中，对于每一个双向边，其实只需要建一正一反两条边就行了，残余网络与反向边合二为一。
成功 AC。
:::info[code]
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1205,M=121005;
const long long inf=1e18;
int n,m,s,t;
int lvl[N],wt[N][N];//层数
struct edge{
int v,w;
int nxt;
}ed[M*2];
int head[N],cnt=2,cur[N];
inline void adde(int u,int v,int w){
ed[cnt]={v,w,head[u]};
head[u]=cnt;
cnt++;
}
queue<int> q;
inline bool bfs(){
for(int i=1;i<=n;i++)lvl[i]=-1;
while(!q.empty())q.pop();
lvl[s]=0;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=ed[i].nxt){
if(lvl[ed[i].v]==-1&&ed[i].w>0){
lvl[ed[i].v]=lvl[u]+1;
if(ed[i].v==t)return 1;
q.push(ed[i].v);
}
}
}
return(lvl[t]!=-1);
}
inline bool gbfs(){
for(int i=1;i<=n;i++)lvl[i]=-1;
while(!q.empty())q.pop();
lvl[s]=0;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=ed[i].nxt){
if(i%2)continue;
if(lvl[ed[i].v]==-1&&ed[i].w>0){
lvl[ed[i].v]=lvl[u]+1;
if(ed[i].v==t)return 1;
q.push(ed[i].v);
}
}
}
return(lvl[t]!=-1);
}
long long dfs(int u,long long cap){//cap:容量
int flow=0;//跑过的流
if(u==t)return cap;
for(int i=cur[u];i&∩i=ed[i].nxt){
cur[u]=i;
int v=ed[i].v,w=ed[i].w;
if(w&&lvl[v]==lvl[u]+1){
int use=dfs(v,min(cap,w*1ll));
if(use==0)lvl[v]=-1;
if(use>0){
ed[i].w-=use;
ed[i^1].w+=use;
cap-=use;
flow+=use;
}
}
}
return flow;
}
long long greed(int u,long long cap){//贪心初始流
int flow=0;//跑过的流
if(u==t)return cap;
for(int i=cur[u];i&∩i=ed[i].nxt){
cur[u]=i;
if((i%2))continue;
int v=ed[i].v,w=ed[i].w;
if(w&&lvl[v]==lvl[u]+1){
int use=greed(v,min(cap,w*1ll));
if(use==0)lvl[v]=-1;
if(use>0){
ed[i].w-=use;
ed[i^1].w+=use;
cap-=use;
flow+=use;
}
}
}
return flow;
}
inline long long dinic(){
long long ans=0;
while(bfs()){
for(int i=1;i<=n;i++)cur[i]=head[i];
ans+=dfs(s,inf);
}
return ans;
}
inline long long gflow(){
long long ans=0;
while(gbfs()){
for(int i=1;i<=n;i++)cur[i]=head[i];
ans+=greed(s,inf);
}
return ans;
}
#ifdef __linux__
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#else
#define getchar _getchar_nolock
#define putchar _putchar_nolock
#endif
inline int read(){
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=(x << 1) + (x << 3)+ch-48;ch=getchar();}
return x*f;
}
inline void write(int x){
if(x<0){putchar('-');x=-x;}
if(x>9)write(x/10);
putchar(x%10+'0');
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
n=read(),m=read(),s=read(),t=read();
for(int i=1;i<=m;++i){
int u,v,w;
u=read(),v=read(),w=read();
wt[u][v]+=w;
}
int fl=0;
for(int bt=28;bt>=0;bt-=4){
long long l=1ll<<bt,r=1ll<<(bt+4);
int wc=0;
for(int u=1;u<=n;u++){
for(int v=u+1;v<=n;v++){
if((wt[u][v]||wt[v][u])&&((l<=wt[u][v]&&wt[u][v]<r)||(l<=wt[v][u]&&wt[v][u]<r))){
adde(u,v,wt[u][v]);
adde(v,u,wt[v][u]);
wt[u][v]=wt[v][u]=0;
wc++;
}
}
}
if(!wc)continue;
if(wc<=n/10)fl+=gflow();
fl+=dinic();
}
write(fl);
return 0;
}
```
:::
### [P5331 [SNOI2019] 通信](https://www.luogu.com.cn/problem/P5331)
这道题看似很强，实际上只需要使用 Primal-Dual 加上 vector 存图即可通过。
学习链接：[《费用流的 Primal-Dual 算法》](https://www.cnblogs.com/tkandi/p/10532774.html)，[《【学习笔记】Primal-Dual 原始对偶算法
》](https://www.cnblogs.com/SoyTony/p/Learning_Notes_about_Primal-Dual_Algorithm.html)。
另外为了增加 cache 命中率，我们希望把数组放进缓存，所以对于数组，可以开小，把 `int` 换为 `short`。
:::info[code]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sg signed
const int N=2002,M=930001,inf=1e18;
short tot=2,s,t,cur[N],n;
int dis[N];
bitset<N> vis;
struct edge{
short v;
sg w,c;
};
vector<edge> G[N];
int h[N],a[N];
sg fb[N][N];
inline void One(sg u,sg v,int w,int c){
G[u].push_back({v,w,c});
fb[v][u]=G[u].size()-1;
}
inline void adde(sg u,sg v,int w,int c){
One(u,v,w,c);
One(v,u,0,-c);
}
struct qn{
short v;
sg w;
inline friend bool operator<(qn aa,qn bb){
return aa.w>bb.w;
}
};
priority_queue<qn> q;
inline bool dijkstra(){
for(int i=s;i<=t;i++)dis[i]=inf;
q.push({s,0});
dis[s]=0;
while(q.size()){
int u=q.top().v;
q.pop();
if(vis[u])continue;
vis[u]=1;
for(auto [v,flow,c]:G[u]){
c+=h[u]-h[v];
if(dis[v]>dis[u]+c&&flow){
dis[v]=dis[u]+c;
q.push({v,dis[v]});
}
}
}
vis.reset();
return dis[t]!=inf;
}
int dfs(int u,int cap){
if(u==t)return cap;
vis[u]=1;
int flow=0;
for(int i=cur[u];i<G[u].size();i++){
cur[u]=i;
int v=G[u][i].v,fl=G[u][i].w,c=G[u][i].c+h[u]-h[v];
if(dis[v]==dis[u]+c&&fl&&!vis[v]){
int use=dfs(v,min(cap,fl));
if(use){
cap-=use;
flow+=use;
G[u][i].w-=use;
G[v][fb[u][v]].w+=use;
}
}
}
vis[u]=0;
return flow;
}
inline int dinic(){
int cost=0;
while(dijkstra()){
memset(cur,0,sizeof(cur));
int fl=dfs(s,inf);
for(int i=s;i<=t;i++)if(dis[i]<inf)h[i]+=dis[i];
cost+=fl*h[t];
}
return cost;
}
inline int read(){
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=(x << 1) + (x << 3)+ch-48;ch=getchar();}
return x*f;
}
#define ind(i) (i)
#define outd(i) (i+n)
signed main(){
int w;
n=read(),w=read();
s=0,t=n*2+1;
for(int i=1;i<=n;i++){
a[i]=read();
}
for(int i=1;i<=n;i++){
adde(s,ind(i),1,0);
adde(outd(i),t,1,0);
adde(ind(i),t,1,w);
}
for(int i=1;i<=n;i++){
for(int j=1;j<i;j++){
int wg=abs(a[i]-a[j]);
if(wg>=w)continue;//剪枝
adde(ind(i),outd(j),1,wg);
}
}
cout<<dinic();
return 0;
}
```
:::
## 几个别的题
### [P4298 [CTSC2008] 祭祀](https://www.luogu.com.cn/problem/P4298)
#### Q1
最小链覆盖的板子，跑一个传递闭包，把间接相连改成直接相连再用 [P2764 最小路径覆盖问题](https://www.luogu.com.cn/problem/P2764)。
#### Q2
和 [P2762 太空飞行计划问题](https://www.luogu.com.cn/problem/P2762) 那一部分有点像，这里是求**反**最大权闭合子图。
[最大权闭合子图](https://blog.csdn.net/qq_45735851/article/details/113811882)。
跑完之后，左边没有匹配的，和右边匹配的，就是最小点覆盖。
#### Q3
对于每一个点，删掉与其**在传递闭包上有边（包括自己）的点**，再跑一边 Q1。如果这个点在最长反链中，那么最长反链长度要 $-1$。据此判断即可。
:::warning[斤氏后人]
重新跑 Q1 时，答案的总点数不是 $n$ 而是 $n-\text{del}$。
:::
不过懒得写网络流了。所以是 $O(n^4)$。
:::info[code]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=155;
vector<int> G[maxn],G0[maxn];
bool can[maxn][maxn],matched[maxn],le[maxn],ri[maxn],q2[maxn],del[maxn],latch[maxn];
int match[maxn],ans=0,n,m;
bool find(int u){//匈牙利
for(int v:G[u]){
if(!matched[v]){
matched[v]=1;
if(!match[v]||find(match[v])){
match[v]=u;
return 1;
}
}
}
return 0;
}
bool find0(int u){//匈牙利
for(int v:G0[u]){
if(!matched[v]){
matched[v]=1;
if(!match[v]||find0(match[v])){
match[v]=u;
return 1;
}
}
}
return 0;
}
void find2(int u){//网络流就不需要这一步了……
le[u]=1;
for(int v:G[u]){
if(!ri[v]){
ri[v]=1;
if(match[v]&&!le[match[v]]){
find2(match[v]);
}
}
}
}
void floyd(){
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
can[i][j]|=can[i][k]&can[k][j];
}
}
}
}
void build(){
floyd();
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(can[i][j])G[i].push_back(j);
}
}
}
void clear(){
for(int i=1;i<=n;i++)G0[i].clear();
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
for(int i=0;i<m;i++){
int u,v;
cin>>u>>v;
can[u][v]=1;
}
build();
for(int i=1;i<=n;i++){
memset(matched,0,sizeof(matched));
if(find(i))ans++;
}
for(int i=1;i<=n;i++){
if(match[i]){
latch[match[i]]=1;//有匹配
}
}
cout<<n-ans<<endl;//Q1
//最大反链=最小链覆盖的补集
for(int i=1;i<=n;i++){
if(!latch[i])find2(i);//需要没有匹配
}
for(int i=1;i<=n;i++){
q2[i]=!((!le[i])||(ri[i]));//不取反就是最大权闭合子图
cout<<q2[i];
}
cout<<endl;
for(int x=1;x<=n;x++){
clear();
memset(del,0,sizeof(del));
memset(match,0,sizeof(match));
int rm=n;
for(int i=1;i<=n;i++){
if(can[x][i]||can[i][x]||i==x){//删除
del[i]=1;
rm--;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(can[i][j]&&!del[i]&&!del[j]){
G0[i].push_back(j);
}
}
}
int tans=0,trans=0;
for(int i=1;i<=n;i++){
memset(matched,0,sizeof(matched));
if(find0(i))tans++;
}
trans=rm-tans;
if(trans+1==n-ans)cout<<1;
else cout<<0;
}
return 0;
}
```
:::
### [P3974 [TJOI2015] 组合数学](https://www.luogu.com.cn/problem/P3974)
这题显然是一个二分套费用流，显然过不了。$V=nm,E=nm$。
$O(Tn^3m^3\log Ans)$ 能过就怪了。不过能得 $30$ 分是好的。
:::info[code]
```cpp
/* This code is from wangxx2012.
This code is from R272171678. */
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int maxn=1e6+10;
const int inf=1e18;
int n,m,s,t,sum;
int a[1010][1010];
struct node{
int to,next,cap,cost;
}e[2*maxn];
int head[maxn],tot=1;
void add(int u,int v,int cap,int cost){
e[++tot].to=v;
e[tot].cap=cap; e[tot].cost=cost;
e[tot].next=head[u];
head[u]=tot;
}
int dis[maxn],cur[maxn];
bool st[maxn],vis[maxn];
bool spfa(){
queue<int> q;
fill(st+1,st+2*n*m+2,0);
fill(dis+1,dis+2*n*m+2,inf);
q.push(s); dis[s]=0; st[s]=1;
while(!q.empty()){
int u=q.front(); q.pop();
st[u]=0;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(dis[v]>dis[u]+e[i].cost&&e[i].cap){
dis[v]=dis[u]+e[i].cost;
if(!st[v]){
q.push(v);
st[v]=1;
}
}
}
}
return dis[t]!=inf;
}
int dfs(int u,int flow,int &mincost){
if(u==t) return flow;
int used=flow;
vis[u]=1;
for(int i=cur[u];i;i=e[i].next){
cur[u]=i;
int v=e[i].to;
if(dis[v]==dis[u]+e[i].cost&&e[i].cap&&!vis[v]){
int rlow=dfs(v,min(used,e[i].cap),mincost);
e[i].cap-=rlow; e[i^1].cap+=rlow;
used-=rlow; mincost+=rlow*e[i].cost;
if(used==0) break;
}
}
vis[u]=0;
return flow-used;
}
int dinic(int &mincost){
int ans=0;
while(spfa()){
memcpy(cur,head,sizeof(head));
ans+=dfs(s,inf,mincost);
}
return ans;
}
int get_id(int x,int y){
return (x-1)*m+y;
}
int get_out(int x,int y){
return get_id(x,y)+n*m;
}
void reset(int k){
s=0,t=2*n*m+1;
memset(head,0,sizeof(head)); tot=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int u_in=get_id(i,j),u_out=get_out(i,j);
if(a[i][j]>0){
add(u_in,u_out,a[i][j],-1); add(u_out,u_in,0,1);
}
if(k-a[i][j]>0){
add(u_in,u_out,k-a[i][j],0); add(u_out,u_in,0,0);
}
}
}
int dx[]={0,1},dy[]={1,0};
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int u_out=get_out(i,j);
for(int type=0;type<2;type++){
int ddx=i+dx[type],ddy=j+dy[type];
if(ddx>=1&&ddx<=n&&ddy>=1&&ddy<=m){
int v_in=get_id(ddx,ddy);
add(u_out,v_in,k,0); add(v_in,u_out,0,0);
}
}
}
}
add(s,1,k,0); add(1,s,0,0);
add(2*n*m,t,k,0); add(t,2*n*m,0,0);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int T;
cin>>T;
while(T--){
cin>>n>>m;
sum=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) cin>>a[i][j],sum+=a[i][j];
}
int l=0,r=sum,ans=sum;
while(l<=r){
int k=(l+r)/2;
reset(k);
int mincost=0;
dinic(mincost);
if(-mincost==sum) ans=k,r=k-1;
else l=k+1;
}
cout<<ans<<endl;
}
return 0;
}
```
:::
### [AT_abc163_e [ABC163E] Active Infants](https://www.luogu.com.cn/problem/AT_ABC163_E)
正解是区间 DP，但是费用流卡卡就能过。