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