网络流基础知识
网络
网络是指一个有向图 \(G=(V,E)\)，对于网络里的每条边 \((u,v)\in E\) 都有一个权值 \(c(u,v)\)，称之为容量，当 \((u,v)\notin E\) 时有 \(c(u,v)=0\)。
网络中有两个特殊的点：源点 \(s\in V\) 和汇点 \(t\in V\),\((s\neq t)\)。
流
设 \(f(u,v)\) 定义二元组 \((u\in V,v\in V)\) 上的实数函数且满足：
- 容量限制：对于每条边，流经该边的流量不得超过该边的容量，即 \(f(u,v)\le c(u,v)\)
- 斜对称性：每条边的流量与其相反边的流量之和为 0，即 \(f(u,v)=-f(v,u)\)
- 流守恒性：从源点流出的流量等于汇点流入的流量，即 \(\forall x\in V -\{s,t\},\sum_{(u,x)\in E}f(u,x)=\sum_{(x,v)\in E}f(x,v)\)
下面给出完整的定义：
\]
那么 \(f\) 称为网络 \(G\) 的流函数。对于 \((u,v)\in E,f(u,v)\) 称为边的流量，\(c(u,v)-f(u,v)\) 称为边的剩余容量。整个网络的流量为 \(\sum_{(s,v)\in E}f(s,v)\)，即从源点流出的所有流量之和。
一般而言也可以把网络流理解为整个图的流量，而这个流量必满足上述三个性质。
增广路
如果一条从源点到汇点的简单路径、路径上所有边的权值都大于零，那么这条路径被称为增广路。
残量网络
假设当前有一网络 \(G=(V,E)\)，则残量网络 \(G_f=(V,E_f)\) 的边定义为 \(G_f(u,v)=c(u,v)-f(u,v)\)。简单地讲，残量网络就是将原网络中的边减去流经这条边的流量。
最大流（dinic 算法）
简述
所有从源点到汇点的路径最终到汇点时候的流量和。
思路
在每次增广之前先对残量网络做 \(\texttt{BFS}\) 分层。具体的，根据点 \(\texttt{u}\) 到 \(\texttt{s}\) 的距离 \(d(u)\) 把整张图分成若干层。令经过 \(\texttt{u}\) 的流量只能流向下一层的结点 \(\texttt{v}\)，即删除 \(\texttt{u}\) 向层数标号相等或更小的结点的出边，我们称 \(G_f\) 剩下的部分为层次图。之后再在层次图上用 \(\texttt{DFS}\) 进行增广，如果最后到汇点的流量不为零，则答案加上流量；否则算法结束，输出答案。
当前弧优化
在每次 \(\texttt{DFS}\) 时，对于一条边 \((u,v)\in E\) 会出现两种情况。
如果当前到 \((u,v)\) 的流量大于等于当前边的流量限制，即 \(flow_{now}\ge c(u,v)\)，这时我们会将 \(c(u,v)\) 作为下一次 \(\texttt{DFS}\) 流量 \(flow_{next}\)，跑了之后，这条边要么满流，要么到汇点时流量没有达到 \(c(u,v)\) 。但是不论如何，这条边没用了！
如果当前到 \((u,v)\) 的流量小于当前边的流量限制，即 \(flow_{now}<c(u,v)\)，这时我们会将 \(flow_{now}\) 作为下一次 \(\texttt{DFS}\) 流量 \(flow_{next}\)，如果无到点时流量没有达到 \(flow_{now}\)，这条边也会没用。否则，这条边在下一次 \(\texttt{DFS}\) 时还会对答案产生贡献，我们就可以用 cur 记录每次合法的点。
例题
代码
#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f3f
using namespace std;
char c;
ll rd(){
ll x = 0, f = 1; c = getchar();
while(! isdigit(c)){if(c == '-')f = - f; c = getchar();}
while(isdigit(c)){x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}
return x * f;
}
const int N = 3e3 + 5;
int n, m, dep[N], hd[N], cur[N], cnt = 1, s = N - 2, t = N - 1;
ll sum;
struct edge{
int nxt, to; ll w;
}e[3000005];
void add(int u, int v, ll w){
e[++cnt] = (edge){hd[u], v, w}; hd[u] = cnt;
}
int bfs(){
memset(dep, 0, sizeof dep);
queue < int > q; q.push(s); dep[s] = 1; cur[s] = hd[s];
while(! q.empty()){
int u = q.front(); q.pop();
for(int i = hd[u]; i; i = e[i].nxt){
int v = e[i].to;
if(! dep[v] and e[i].w){
cur[v] = hd[v];
dep[v] = dep[u] + 1;
q.push(v);
}
}
}
return dep[t];
}
ll dfs(int u, ll lim){
if(u == t or ! lim)return lim;
ll k, flow = 0;
for(int &i = cur[u]; i and lim; i = e[i].nxt){
int v = e[i].to; ll f = e[i].w;
if((dep[v] == dep[u] + 1) and (k = dfs(v, min(lim, f)))){
e[i].w -= k; e[i ^ 1].w += k;
flow += k; lim -= k;
if(! lim)break;
}
}
if(! flow)dep[u] = N;
return flow;
}
ll dinic(){
ll maxflow = 0, k;
while(bfs()){
while(k = dfs(s, INF))maxflow += k;
}
return maxflow;
}
signed main(){
n = rd(); m = rd(); s = rd(); t = rd();
for(int i = 1; i <= m; ++i){
int u = rd(), v = rd(); ll w = rd();
add(u, v, w); add(v, u, 0);
}
cout << dinic();
return 0;
}
最大流之预流推进
\(\texttt{Push-Relabel}\) 算法
此算法在求解过程中忽略流守恒性，并每次对一个结点更新信息，以求解最大流。
通用的预流推进算法
预流推进通过每次单点更新的方法求解最大流。
在算法中，我们维护的流函数 \(f(u,v)\) 不一定具有流守恒性。对于每个点，我们允许流入结点的流量超过流出结点的流量，而超过部分我们定义为这个结点 \(u(u\in V-{s,t})\) 的超额流 \(exc(u)\)：
\]
如果 \(exc(u)>0\)，则结点 \(u\) 溢出，但溢出结点不包括源点汇点。
预流推进最重要的是维护每个结点的高度 \(h(u)\)，每次推送超额流时，只能向高度小于当前点的点推送；如果当前点的相邻点没有比其高度更小的，就修改当前点的高度。
高度函数
预流推进维护以下的一个映射 \(h:V\to N\)：
- \(h(s)=|V|,h(t)=0\)
- \(\forall(u,v)\in E_f,h(u)\le h(v) + 1\)
其中 \(h\) 是残量网络 \(G_f=(V_f,E_f)\) 的高度函数。而每次推送超额流当且仅当 \((u,v)\in E_f,h(u)=h(v) + 1\)。
推进（Push）
当一个结点 \(u\) 溢出，且存在一个结点 \(v((u,v)\in E_f,h(u)=h(v)+1,c(u,v)-f(u,v)\ge0)\)，这时进行 \(\texttt{Push}\) 操作。每次操作，我们将超额流最大限度推送，而且在推送中我们只管超额流和当前剩余可通行流量限制的最小值，不用管结点是否溢出。如果 \((u,v)\) 在操作完后满流就删除。
修改高度（Relabel）
修改高度又叫重贴标签，如果 \(exc(u)>0,\forall(u,v)\in E_f,h(u)\le h(v)\)，就重贴标签。
每次重贴标签将 \(h(u)\) 修改为 \(\min_{(u,v)\in E_f}h(v)+1\)。
过程
还是每次进行 \(\texttt{BFS}\) 操作，遇到满足条件的结点就执行操作。
\(\texttt{HLPP}\) 算法
相较于 \(\texttt{Push-Relabel}\) 算法，\(\texttt{HLPP}\) 算法在每次选择结点时都优先选择高度最高的点。
\(\texttt{BFS}\) 优化
个人觉得其实这并不算严格意义来讲的优化，\(\texttt{BFS}\) 与 \(\texttt{dinic}\) 算法的完全一样，只不过在 \(\texttt{HLPP}\) 算法中我们用高度函数 \(h(u)\) 代替 \(\texttt{dinic}\) 算法中的层数 \(d(u)/dep(u)\)。
\(\texttt{GAP}\) 优化
在每次重贴标签时，我们直接让结点的高度变成 \(n+1\)，这样能尽快退回源点，减少重贴标签的操作。
我们可以使用 \(2n\) 个桶 b,b[i] 记录所有高度为 \(i\) 的溢出结点，每次从高度小于 \(n+1\) 的最高的高度取点。
例题
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll rd(){
ll x = 0, f = 1; char c = getchar();
while(! isdigit(c)){if(c == '-')f = - f; c = getchar();}
while(isdigit(c)){x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}
return x * f;
}
const int N = 1205, M = 1.2e5 + 5, INF = 0x3f3f3f3f;
int n, m, s, t, hd[N], cnt = 1;
struct edge{
int nxt, to; ll w;
}e[M << 1];
void add(int u, int v, ll w){
e[++cnt] = (edge){hd[u], v, w}; hd[u] = cnt;
}
int h[N], gap[N], height;
ll exc[N];
stack < int > b[N];
bool pushin(int u){
bool op = u == s;
for(int i = hd[u]; i; i = e[i].nxt){
int v = e[i].to; ll w = e[i].w;
if(! w or ! op and h[u] != h[v] + 1 or h[u] == INF)continue;
ll k = op ? w : min(w, exc[u]);
if(v != s and v != t and ! exc[v])b[h[v]].push(v), height = max(height, h[v]);
exc[u] -= k; exc[v] += k; e[i].w -= k; e[i ^ 1].w += k;
if(! exc[u])return 0;
}
return 1;
}
void relabel(int u){
h[u] = INF;
for(int i = hd[u]; i; i = e[i].nxt)if(e[i].w)h[u] = min(h[u], h[e[i].to]);
if(++h[u] < n){
b[h[u]].push(u);
height = max(height, h[u]);
++gap[h[u]];
}
}
bool bfs(){
memset(h, 0x3f, sizeof h);
queue < int > q;
q.push(t); h[t] = 0;
while(! q.empty()){
int u = q.front(); q.pop();
for(int i = hd[u]; i; i = e[i].nxt){
int v = e[i].to;
if(e[i ^ 1].w and h[v] > h[u] + 1)h[v] = h[u] + 1, q.push(v);
}
}
return h[s] != INF;
}
int sel(){
while(b[height].empty() and height > - 1)--height;
return ~ height ? b[height].top() : 0;
}
ll HLPP(){
if(! bfs)return 0;
memset(gap, 0, sizeof gap);
for(int i = 1; i <= n; ++i)if(h[i] != INF)++gap[h[i]];
h[s] = n; pushin(s);
int u;
while(u = sel()){
b[height].pop();
if(pushin(u)){
if(! --gap[h[u]])
for(int i = 1; i <= n; ++i)if(i != s and i != t and h[i] > h[u] and h[i] < n + 1)h[i] = n + 1;
relabel(u);
}
}
return exc[t];
}
signed main(){
n = rd(); m = rd(); s = rd(); t = rd();
for(int i = 1; i <= m; ++i){
int u = rd(), v = rd(), w = rd();
add(u, v, w); add(v, u, 0);
}
printf("%lld", HLPP());
return 0;
}
最大流最小割定理
割
在一个网络中，一个 \(s/t\) 割 \([S,T]\) 是由从源点集合 \(S\) 到 汇点集合 \(T\) 的所有边构成的集合，其中 \(S\) 和 \(T\) 是对点集合的划分，且 \(s\in S,t\in T\)。
割的容量
割 \([S,T]\) 的容量是从 \(S\) 到 \(T\) 的边的总容量，记为 \(c(S,T)\)，即：
\]
结点集的净流量
我们可以将净流量的概念推广到由结点构成的集合 \(\texttt{U}\) 上。令 \(f^+(U)\) 表示离开 \(\texttt{U}\) 的所有边上的总流量，\(f^−(U)\) 表示进入 \(\texttt{U}\) 的所有边上的流量的总和。则从 \(\texttt{U}\) 流出的净流量定义为：
\]
引理
对于网络中的一个可行流 \(f\)，其流的值 \(|f|\) 等于 \([S,T]\) 割中，结点集合 \(S\) 的净流量 \(f(S)\)。
证明：
考虑根据 \(S\) 的大小进行归纳证明。
- 基本情况：当 \(S\) 只有一个结点的时候，\(S=\left\{s\right\}\)，根据流的定义有\(|f|=f^+(s)-f^-(s)=f(S)\)。
- 归纳步骤：假设当 \(S\) 中有 \(k\) 个点时，有 \(|f|=f(S)\) 成立。接下来我们需要证明，将一个点从 \(T\) 变到 \(S\) 后，净流量不变。
假设现在将点 \(u\) 从 \(T\) 变到 \(S\) 中。则 \(u\) 关于 \([S,T]\) 割的流有四类：
- 从 \(S\) 流到 \(u\) 的流量总和；
- 从 \(T\) 流到 \(u\) 的流量总和；
- 从 \(u\) 流到 \(S\) 的流量总和；
- 从 \(u\) 流到 \(T\) 的流量总和；
设以上四种情况的流量总和分别为 \(A\)、\(B\)、\(C\)、\(D\)。因为网络有流守恒，所以流入流量等于流出流量，即：\(A+B=C+D\ \ \ \ \ (1)\)
在 \(u\) 到 \(S\) 前，其对 \(S\) 的净流量贡献为 \(A-C\)；在 \(u\) 到 \(S\) 后，其对 \(S\) 的净流量贡献为 \(D-B\)。
根据 \((1)\) 可得：\(A-C=D-B\)。可以发现等式两边对应了 \(u\) 到 \(S\) 前后的贡献，而这两个部分相等，说明 \(u\) 到 \(S\) 后贡献不变。
所以当 \(S\) 中有 \(k+1\) 个点时，也有 \(|f|=f(S)\) 成立。证毕。
最大流最小割定理
最大流最小割定理：在任意网络中，设 \(maxflow\) 为最大流，\([S,T]\) 是一个最小割，则 \(maxflow=c(S,T)\)。
证明：
证明 \(maxflow=c(S,T)\)，等价于证明 \(maxflow\le c(S,T)\) 且 \(maxflow\ge c(S,T)\)。
有了之前证的引理，可得：
|f|&=f(S)\\
&=f^+(S)-f^-(S)\\
&\le f^+(S)\\
&\le c(S,T)
\end{align}
\]
\(\therefore maxflow\le c(S,T)\)
证明 \(maxflow\ge c(S,T)\)，等价于证明网络中存在流 \(f'\) 和割 \([S',T']\)，使得 \(|f'|=c(S',T')\)。
即 \(\exists f',[S',T']\Longrightarrow |f'|=c(S',T')\)。
我们可以用 \(\texttt{Ford-Fulkerson}\) 做法的结果来证明。当算法结束后，残量网络 \(G_f\) 中不存在增广路，即 \(s\) 和 \(t\) 不连通。
假设有 \((u,v)\in E,u\in S',v\in T'\)，则必有 \(f(u,v)=c(u,v)\)；否则 \((u,v)\in E_f\)，与假设矛盾。而 \((v,u)\) 就一定为零。所以：
f(S',T')&=\sum\limits_{u\in S'}\sum\limits_{v\in T'}f(u,v)-f(v,u)\\
&=\sum\limits_{u\in S'}\sum\limits_{v\in T'}f(u,v)-0\\
&=c(S',T')
\end{align}
\]
\(\because maxflow\ge |f'|=c(S',T')\ge c(S,T)\)
$\therefore maxflow\ge c(S,T) $
\(\therefore maxflow= c(S,T)\)
证毕。
最大流的一些题
P3254 圆桌问题
题目描述
有来自 \(m\) 个不同单位的代表参加一次国际会议。第 \(i\) 个单位派出了 \(r_i\) 个代表。
会议的餐厅共有 \(n\) 张餐桌，第 \(i\) 张餐桌可容纳 \(c_i\) 个代表就餐。
为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。请给出一个满足要求的代表就餐方案。
题解
源点向每个单位连边，容量为单位人数；每个单位向每张餐桌连边，容量为 \(1\)；每张餐桌向汇点连边，容量为餐桌可容纳人数。然后跑 \(\texttt{dinic}\)，如果答案与单位总人数不相等则无解；否则对于每个单位暴力找与餐桌连边为零的输出。
代码
#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f3f
using namespace std;
ll rd(){
ll x = 0, f = 1; char c = getchar();
while(! isdigit(c)){if(c == '-')f = - f; c = getchar();}
while(isdigit(c)){x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}
return x * f;
}
const int N = 1e5 + 5;
int n, m, dep[N], hd[N], cur[N], cnt = 1, s = 1, t = N - 1;
ll sum;
struct edge{
int nxt, to; ll w;
}e[N << 1];
void add(int u, int v, int w){
e[++cnt] = (edge){hd[u], v, w}; hd[u] = cnt;
}
int bfs(){
memset(dep, 0, sizeof dep);
queue < int > q; q.push(s); dep[s] = 1;
while(! q.empty()){
int u = q.front(); q.pop();
for(int i = hd[u]; i; i = e[i].nxt){
int v = e[i].to;
if(! dep[v] and e[i].w){
dep[v] = dep[u] + 1;
q.push(v);
}
}
}
return dep[t];
}
ll dfs(int u, ll lim){
if(u == t or ! lim)return lim;
ll k, flow = 0;
for(int &i = cur[u]; i; i = e[i].nxt){
int v = e[i].to; ll f = e[i].w;
if((dep[v] == dep[u] + 1) and (k = dfs(v, min(lim, f)))){
e[i].w -= k; e[i ^ 1].w += k;
flow += k; lim -= k;
}
}
if(! flow)dep[u] = N;
return flow;
}
ll dinic(){
ll maxflow = 0, k;
while(bfs()){
memcpy(cur, hd, sizeof hd);
while(k = dfs(s, INF))maxflow += k;
}
return maxflow;
}
signed main(){
n = rd(); m = rd();
for(int i = 1; i <= n; ++i){
ll u = rd(); sum += u;
add(s, i + 1, u); add(i + 1, s, 0);
for(int j = 1; j <= m; ++j)add(i + 1, j + n + 1, 1), add(j + n + 1, i + 1, 0);
}
//cout << sum << '\n';
for(int i = 1; i <= m; ++i){
ll u = rd();
add(i + n + 1, t, u); add(t, i + n + 1, 0);
}
int ans = dinic(); //cout << ans << '\n';
if(ans != sum)return puts("0"), 0;
puts("1");
for(int u = 1; u <= n; ++u){
for(int i = hd[u + 1]; i; i = e[i].nxt){
int v = e[i].to;
if(v == s)continue;
if(! e[i].w)printf("%d ", v - n - 1);
}
puts("");
}
return 0;
}
P2766 最长不下降子序列问题
题目描述
给定正整数序列 \(x_1 \ldots, x_n\)。
- 计算其最长不下降子序列的长度 \(s\)。
- 如果每个元素只允许使用一次，计算从给定的序列中最多可取出多少个长度为 \(s\) 的不下降子序列。
- 如果允许在取出的序列中多次使用 \(x_1\) 和 \(x_n\)（其他元素仍然只允许使用一次），则从给定序列中最多可取出多少个不同的长度为 \(s\) 的不下降子序列。
令 \(a_1, a_2, \ldots, a_s\) 为构造 \(S\) 时所使用的下标，\(b_1, b_2, \ldots, b_s\) 为构造 \(T\) 时所使用的下标。且 \(\forall i \in [1,s-1]\)，都有 \(a_i \lt a_{i+1}\)，\(b_i \lt b_{i+1}\)。则 \(S\) 和 \(T\) 不同，当且仅当 \(\exists i \in [1,s]\)，使得 \(a_i \neq b_i\)。
题解
第一问 \(\texttt{LCS}\) 直接做。
第二问因为每个点经过多次，考虑拆点做。对于第一问每个 i>j&&dp[i]==dp[j]+1&&a[i]>=a[j] 连一条容量为一的边，如果 dp[i]==1 就从源点向 \(i\) 连；如果 dp[i]==ans1 就从 \(i\) 连向汇点。然后跑 \(\texttt{dinic}\)。
第三问是第二问的变式，即可以多次使用第一个点和最后一个点。判一下最后一个点的 dp[i]==ans1，然后源点到 \(1\) 和最后到汇点连一条 INF 的边。继续在残量网络上跑 \(\texttt{dinic}\)。
代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define Fl(i, l, r) for(int i = l; i <= r; i++)
#define Fr(i, r, l) for(int i = r; i >= l; i--)
const int N = 505, M = 2e6 + 5, INF = 1e9;
int n, a[N], ans1, ans2, ans3, dp[N], s, t = 5e3;
int hd[M], nxt[M], to[M], w[M], now[M], cnt;
void add(int u, int v, int dis){
nxt[++cnt] = hd[u]; hd[u] = cnt; to[cnt] = v; now[cnt] = u; w[cnt] = dis;
nxt[++cnt] = hd[v]; hd[v] = cnt; to[cnt] = u; now[cnt] = v; w[cnt] = dis;
}
int f[100 * N];
bool bfs(int s, int t){
memset(f, 0, sizeof f);
queue < int > q; q.push(s); f[s] = 1;
while(! q.empty()){
int u = q.front(); q.pop();
if(u == t)return true;
for(int i = hd[u]; i; i = nxt[i]){
int v = to[i], d = w[i];
if(f[v] == 0 and d)q.push(v), f[v] = f[u] + 1;
}
}
return false;
}
int dfs(int u, int maxflow, int t){
if(u == t)return maxflow;
int ret = 0;
for(int i = hd[u]; i and ret < maxflow; i = nxt[i]){
int v = to[i], d = w[i];
if(f[v] == f[u] + 1 and d){
int minflow = min(maxflow - ret, d);
d = dfs(v, minflow, t);
w[i] -= d; w[i ^ 1] += d; ret += d;
}
}
if(! ret)f[u] = M;
return ret;
}
void solve(){
cin >> n;
if(n == 1){cout << 1 << '\n' << 1 << '\n' << 1; return;}
Fl(i, 1, n)cin >> a[i]; dp[1] = 1;
Fl(i, 2, n){
int k = 0;
Fl(j, 1, i - 1)if(a[j] <= a[i] and dp[k] < dp[j])k = j;
dp[i] = dp[k] + 1;
}
Fl(i, 1, n)ans1 = max(ans1, dp[i]);
Fl(i, 1, n){
if(dp[i] == 1)add(s, i, 1);
if(dp[i] == ans1)add(i + n, t, 1);
add(i, i + n, 1);
}
Fl(i, 1, n)Fl(j, 1, i - 1)if(a[i] >= a[j] and dp[j] + 1 == dp[i])add(j + n, i, 1);
while(bfs(s, t))ans2 += dfs(s, INF, t); ans3 = ans2;
add(s, 1, INF); add(1, 1 + n, INF); if(dp[n] == ans1)add(n, 2 * n, INF), add(2 * n, t, INF);
while(bfs(s, t))ans3 += dfs(s, INF, t);
cout << ans1 << '\n' << ans2 << '\n' << ans3;
}
signed main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
solve(); return 0;
}
[AGC038F] Two Permutations
题目描述
给定两个 \(0 \sim (N - 1)\) 的排列 \(\{P_0, P_1, \ldots , P_{N - 1}\}\) 和 \(\{Q_0, Q_1, \ldots , Q_{N - 1}\}\)。
要求构造两个 \(0 \sim (N - 1)\) 的排列 \(\{A_0, A_1, \ldots , A_{N - 1}\}\) 和 \(\{B_0, B_1, \ldots , B_{N - 1}\}\)。
且必须满足条件：
- \(A_i\) 要么等于 \(i\)，要么等于 \(P_i\)。
- \(B_i\) 要么等于 \(i\)，要么等于 \(Q_i\)。
你需要最大化 \(A_i \ne B_i\) 的下标 \(i\) 的数量，输出这个最大值。
题解
对于每个排列，我们可以把它分解成若干个置换环。对于每个置换环 \(A\)，我们只有两种选择：\(A_i\) 变或不变。如果一个置换环上其中一点确定，那么整个环也就确定了，因为要确保数字唯一性。所以我们可以先把置换环处理出来，再把每个环当做一个点做。
对于给定的两个排列，一共有五种不同情况。
- \(i=P_i=Q_i\)，直接答案减一；
- \(i=P_i\ne Q_i\)，只有 \(Q_i\) 才会对答案产生影响，如果选 \(i\)，整个答案就会减一，否则不变；
- \(i=Q_i\ne P_i\)，与上一种类似，不再赘述；
- \(i\ne P_i=Q_i\)，如果两个同选 \(i\) 或自己则答案减一；
- \(i\ne P_i\ne Q_i\)，如果两个同选下标 \(i\) 则答案减一。
对于这五种情况，每个置换环有两种选择：选择自己的下标或者自己的值，可以想到最小割。
然后我们将上面五种情况的结果改一下：
- \(i=P_i=Q_i\)，直接答案减一；
- \(i=P_i\ne Q_i\)，如果 \(Q_i\) 选 \(i\)，\(Q_i\) 所在环向汇点连容量为一的边；
- \(i=Q_i\ne P_i\)，与上一种类似，不再赘述；
- \(i\ne P_i=Q_i\)，\(P_i\) 与 \(Q_i\) 所在环互相连容量为一的边；
- \(i\ne P_i\ne Q_i\)，\(Q_i\) 所在环向 \(P_i\) 所在环连容量为一的单向边。
最后直接跑最大流，然后再用总的个数减去跑出来的结果即可。
代码
#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
ll rd(){
ll x = 0, f = 1; char c = getchar();
while(! isdigit(c)){if(c == '-')f = - f; c = getchar();}
while(isdigit(c)){x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}
return x * f;
}
const int N = 2e5 + 5;
int n, s, t, hd[N], cnt = 1, cur[N], ans;
int a[N], b[N], ra[N], rb[N], d[N], top;
struct edge{
int nxt, to, w;
}e[N << 1];
void add(int u, int v, int w){
e[++cnt] = (edge){hd[u], v, w}; hd[u] = cnt;
}
int bfs(){
memset(d, 0, sizeof d);
queue < int > q;
q.push(s); d[s] = 1; cur[s] = hd[s];
while(! q.empty()){
int u = q.front(); q.pop();
for(int i = hd[u]; i; i = e[i].nxt){
int v = e[i].to, w = e[i].w;
if( ! d[v] and w){
d[v] = d[u] + 1;
cur[v] = hd[v];
q.push(v);
}
}
}
return d[t];
}
int dfs(int u, int lim){
if(u == t or ! lim)return lim;
int k, flow = 0;
for(int &i = cur[u]; i and lim; i = e[i].nxt){
int v = e[i].to, f = e[i].w;
if(d[v] == d[u] + 1 and (k = dfs(v, min(lim, f)))){
e[i].w -= k; e[i ^ 1].w += k;flow += k; lim -= k;
}
}
if(! flow)d[u] = t + 1;
return flow;
}
int dinic(){
int res = 0, k;
while(bfs()){
while(k = dfs(s, INF))res += k;
}
return res;
}
signed main(){
n = rd();
for(int i = 1; i <= n; ++i)a[i] = rd() + 1;
for(int i = 1; i <= n; ++i)b[i] = rd() + 1;
for(int i = 1; i <= n; ++i)if(! ra[i]){
ra[i] = a[i] != i ? ++top : top;
int x = a[i];
while(x != i)ra[x] = top, x = a[x];
}
for(int i = 1; i <= n; ++i)if(! rb[i]){
rb[i] = b[i] != i ? ++top : top;
int x = b[i];
while(x != i)rb[x] = top, x = b[x];
}
s = top + 1, t = s + 1;
for(int i = 1; i <= n; ++i)
if(a[i] == i and b[i] == i)++ans;
else if(a[i] != i and b[i] != i){
if(a[i] == b[i]){
add(ra[i], rb[i], 1); add(rb[i], ra[i], 1);
add(ra[i], rb[i], 0); add(rb[i], ra[i], 0);
}
else{
add(rb[i], ra[i], 1); add(ra[i], rb[i], 0);
}
}
else{
if(a[i] == i)add(rb[i], t, 1), add(t, rb[i], 0);
else add(ra[i], s, 0), add(s, ra[i], 1);
}
printf("%d", n - ans - dinic());
return 0;
}
费用流
概念
网络中，每个边除了流量，现在还有一个单位费用 \(w(u,v)\)，这条边的费用相当于它的单位费用乘上它的流量，在求最大流的同时，保证费用最小。
\(\texttt{SSP}\) 算法
其实就是一个裸贪心，每次找单位费用最小的增广路进行增广，直到图上不存在增广路为止。如果有负环要消环。
将 \(\texttt{Dinic}\) 算法中的寻找增广路的过程，替换为用最短路算法寻找单位费用最小的增广路即可。
时间复杂度 \(O(nmk)\)。
例题
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll rd(){
ll x = 0, f = 1; char c = getchar();
while(! isdigit(c)){if(c == '-')f = - f; c = getchar();}
while(isdigit(c)){x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}
return x * f;
}
const int N = 5005, M = 5e4 + 5;
int n, m, s, t;
int pren[N], pree[N], val[N], fl[N];
int hd[N], cnt = 1;
bool vis[N];
struct edge{
int nxt, to, d, w;
}e[M << 1];
void add(int u, int v, int d, int w){
e[++cnt] = (edge){hd[u], v, d, w}; hd[u] = cnt;
}
bool SPFA(){
memset(val, 0x3f, sizeof val);
memset(fl, 0x3f, sizeof fl);
memset(vis, 0, sizeof vis);
queue < int > q;
pren[t] = - 1; vis[s] = 1; q.push(s); val[s] = 0;
while(! q.empty()){
int u = q.front(); q.pop();
vis[u] = 0;
for(int i = hd[u]; i; i = e[i].nxt){
int v = e[i].to, d = e[i].d, w = e[i].w;
if(d and val[v] > val[u] + w){
val[v] = val[u] + w;
if(! vis[v]){
vis[v] = 1;
q.push(v);
}
fl[v] = min(fl[u], d);
pren[v] = u; pree[v] = i;
}
}
}
return pren[t] != - 1;
}
int ansfl, ansv;
void MCMF(){
while(SPFA()){
ansfl += fl[t];
ansv += fl[t] * val[t];
int x = t;
while(x != s){
e[pree[x]].d -= fl[t];
e[pree[x] ^ 1].d += fl[t];
x = pren[x];
}
}
}
signed main(){
n = rd(); m = rd(); s = rd(); t = rd();
for(int i = 1; i <= m; ++i){
int u = rd(), v = rd(), fl = rd(), w = rd();
add(u, v, fl, w); add(v, u, 0, - w);
}
MCMF();
printf("%d %d", ansfl, ansv);
return 0;
}
例题
P3358 最长k可重区间集问题
题目描述
给定实直线 \(\text{L}\) 上 \(n\) 个开区间组成的集合 \(\mathbf{I}\)，和一个正整数 \(k\)，试设计一个算法，从开区间集合 \(\mathbf{I}\) 中选取出开区间集合 \(\mathbf{S}\subseteq\mathbf{I}\)，使得在实直线 \(\text{L}\) 上的任意一点 \(x\)，\(\text{S}\) 中包含 \(x\) 的开区间个数不超过 \(k\)，且 \(\sum_{z\in\text{S}}\lvert z\rvert\) 达到最大（\(\lvert z\rvert\) 表示开区间 \(z\) 的长度）。
这样的集合 \(\mathbf{S}\) 称为开区间集合 \(\mathbf{I}\) 的最长 \(k\) 可重区间集。\(\sum_{z\in\text{S}}\lvert z\rvert\) 称为最长 \(k\) 可重区间集的长度。
对于给定的开区间集合 \(\mathbf{I}\) 和正整数 \(k\)，计算开区间集合 \(\mathbf{I}\) 的最长 \(k\) 可重区间集的长度。
题解
可以把直线上的每个数看成一个点，每个点向后连一条容量为 \(\texttt{k}\)，费用为零的边；区间左端点向右端点连一条容量为一，费用为区间长度的负数的边（因为求最小费用和题目最长重区间相反，所以取反两次即可）。源点向第一个点连一条容量为 \(\texttt{k}\)，费用为零的边；最后一个点向汇点连一条容量为 \(\texttt{k}\)，费用为零的边。
这样直接跑费用流会寄，因为有很多无用的点，所以离散化一下，再处理区间端点即可。
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll rd(){
ll x = 0, f = 1; char c = getchar();
while(! isdigit(c)){if(c == '-')f = - f; c = getchar();}
while(isdigit(c)){x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}
return x * f;
}
const int N = 1005, M = 1e5 + 5;
int n, k, s, t;
int pren[N], pree[N], val[N], fl[N];
int hd[N], cnt = 1;
bool vis[N];
struct edge{
int nxt, to, d, w;
}e[M];
void add(int u, int v, int d, int w){
e[++cnt] = (edge){hd[u], v, d, w}; hd[u] = cnt;
}
bool SPFA(){
memset(val, 0x3f, sizeof val);
memset(fl, 0x3f, sizeof fl);
memset(vis, 0, sizeof vis);
queue < int > q;
pren[t] = - 1; vis[s] = 1; q.push(s); val[s] = 0;
while(! q.empty()){
int u = q.front(); q.pop();
vis[u] = 0;
for(int i = hd[u]; i; i = e[i].nxt){
int v = e[i].to, d = e[i].d, w = e[i].w;
if(d and val[v] > val[u] + w){
val[v] = val[u] + w;
if(! vis[v]){
vis[v] = 1;
q.push(v);
}
fl[v] = min(fl[u], d);
pren[v] = u; pree[v] = i;
}
}
}
return pren[t] != - 1;
}
int ansv;
void MCMF(){
while(SPFA()){
ansv += fl[t] * val[t];
int x = t;
while(x != s){
e[pree[x]].d -= fl[t];
e[pree[x] ^ 1].d += fl[t];
x = pren[x];
}
}
}
int l[N], r[N], a[N], top;
signed main(){
n = rd(); k = rd();
for(int i = 1; i <= n; ++i){
a[++top] = l[i] = rd();
a[++top] = r[i] = rd();
}
sort(a + 1, a + 1 + top);
top = unique(a + 1, a + 1 + top) - a - 1;
s = top + 1; t = s + 1;
for(int i = 1; i <= n; ++i){
int t = r[i] - l[i];
l[i] = lower_bound(a + 1, a + 1 + top, l[i]) - a;
r[i] = lower_bound(a + 1, a + 1 + top, r[i]) - a;
add(l[i], r[i], 1, - t); add(r[i], l[i], 0, t);
}
add(s, 1, k, 0); add(1, s, 0, 0);
add(top, t, k, 0); add(t, top, 0, 0);
for(int i = 1; i < top; ++i)add(i, i + 1, k, 0), add(i + 1, i, 0, 0);
MCMF();
printf("%d", - ansv);
return 0;
}
P2469 [SDOI2010] 星际竞速
题目描述
10 年一度的银河系赛车大赛又要开始了。作为全银河最盛大的活动之一，夺得这个项目的冠军无疑是很多人的梦想，来自杰森座 \(\alpha\) 星的悠悠也是其中之一。
赛车大赛的赛场由 \(N\) 颗行星和 \(M\) 条双向星际航路构成，其中每颗行星都有一个不同的引力值。大赛要求车手们从一颗与这 \(N\) 颗行星之间没有任何航路的天体出发，访问这 \(N\) 颗行星每颗恰好一次，首先完成这一目标的人获得胜利。
由于赛制非常开放，很多人驾驶着千奇百怪的自制赛车来参赛。这次悠悠驾驶的赛车名为超能电驴，这是一部凝聚了全银河最尖端科技结晶的梦幻赛车。作为最高科技的产物，超能电驴有两种移动模式：高速航行模式和能力爆发模式。在高速航行模式下，超能电驴会展开反物质引擎，以数倍于光速的速度沿星际航路高速航行。在能力爆发模式下，超能电驴脱离时空的束缚，使用超能力进行空间跳跃——在经过一段时间的定位之后，它能瞬间移动到任意一个行星。
天不遂人愿，在比赛的前一天，超能电驴在一场离子风暴中不幸受损，机能出现了一些障碍：在使用高速航行模式的时候，只能由每个星球飞往引力比它大的星球，否则赛车就会发生爆炸。
尽管心爱的赛车出了问题，但是悠悠仍然坚信自己可以取得胜利。他找到了全银河最聪明的贤者——你，请你为他安排一条比赛的方案，使得他能够用最少的时间完成比赛。
题解
对于“高速航行模式”和“能力爆发模式”分别建点，因为每个点只用去一次，所以所有边容量为一。对于“能力爆发模式”，由于任意点都可以到当前点，所以直接从源点向所有“能力爆发模式”点连边，费用为时间；对于“高速航行模式”，从源点向所有“高速航行模式”点连边，费用为零，再从编号小的点向大的“能力爆发模式”的点正常连边，费用为时间。最后从所有“能力爆发模式”点向汇点连边，费用为零即可。
代码
#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
ll rd(){
ll x = 0, f = 1; char c = getchar();
while(! isdigit(c)){if(c == '-')f = - f; c = getchar();}
while(isdigit(c)){x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}
return x * f;
}
const int N = 1e4 + 5, M = 1e5 + 5;
int n, m, s, t, top, a[N];
int pren[N], pree[N], val[N], fl[N];
int hd[N], cnt = 1;
bool vis[N];
struct edge{
int nxt, to, d, w;
}e[M];
void add(int u, int v, int d, int w){
e[++cnt] = (edge){hd[u], v, d, w}; hd[u] = cnt;
}
bool SPFA(){
memset(val, 0x3f, sizeof val);
memset(fl, 0x3f, sizeof fl);
memset(vis, 0, sizeof vis);
queue < int > q; int qwq = 0;
pren[t] = - 1; vis[s] = 1; q.push(s); val[s] = 0;
while(! q.empty()){
int u = q.front(); q.pop();
vis[u] = 0;
for(int i = hd[u]; i; i = e[i].nxt){
int v = e[i].to, d = e[i].d, w = e[i].w;
if(d and val[v] > val[u] + w){
val[v] = val[u] + w;
if(! vis[v]){
vis[v] = 1;
q.push(v);
}
fl[v] = min(fl[u], d);
pren[v] = u; pree[v] = i;
}
}
}
return pren[t] != - 1;
}
int ansv;
void MCMF(){
while(SPFA()){
ansv += fl[t] * val[t];
int x = t;
while(x != s){
e[pree[x]].d -= fl[t];
e[pree[x] ^ 1].d += fl[t];
x = pren[x];
}
}
}
signed main(){
n = rd(); m = rd(); s = N - 3, t = s + 1;
for(int i = 1; i <= n; ++i){
a[i] = rd();
add(s, i, 1, a[i]); add(i, s, 0, - a[i]);
add(s, i + n, 1, 0); add(i + n, s, 0, 0);
add(i, t, 1, 0); add(t, i, 0, 0);
}
for(int i = 1; i <= m; ++i){
int u = rd(), v = rd(), time = rd();
if(u > v)swap(u, v);
add(u + n, v, 1, time); add(v, u + n, 0, - time);
}
MCMF();
printf("%d", ansv);
return 0;
}
