「网络流24题」最长不下降子序列问题-题解

题目传送门: 「Luogu P2766」最长不下降子序列问题

题目大意

给定正整数序列$x_1, x_2, …, x_n$

  1. 计算其 最长不下降子序列 的长度$S$
  2. 如果每个元素只允许使用一次,计算从给定的序列中最多可取出多少个长度为$S$的不下降子序列
  3. 如果允许在取出的序列中多次使用$x_1$和$x_n$,其他元素仍然只允许使用一次,则从给定序列中最多可取出多少个 不同 的长度为$S$的不下降子序列

题解

第一问

动态规划
状态转移方程:$\mathtt{f[i]=max_{1≤j<i&&x_j≤x_i}\{f[j]+1\}}$
初值: $\mathtt{f[0]=0}$
结果: $\mathtt{max_{1\leq i\leq n}f[i]}$

第二问

将每个点(索引)拆成两个点
应用了分层图的思想, 把图每个顶点$\mathtt{i}$按照$\mathtt{f[i]}$的不同分为了若干层
这样图中从$s$出发到$t$的任何一条路径都是一个满足条件的最长上升子序列
由于序列中每个点要不可重复地取出,需要把每个点拆分成两个点
单位网络的最大流就是增广路的条数,所以最大流量就是第二问结果。

  1. 从 源点 向 每个$\mathtt{f[i]==1}$的点i的左点 建一条 容量为1 的边
  2. 从 每个点的左点 向 其右点 建一条 容量为1 的边
  3. 从 $\mathtt{f[i]==S}$的点i的右点 向 汇点 建一条 容量为1 的边
  4. 对于$j<i$,若$\mathtt{x_j\leq x_i && f[i] == f[j] + 1}$,则从 点j的右点 向 点i的左点 建一条 容量为1 的边

第三问

要求$x_1$和$x_n$可以重复使用,只需取消这两个点相关边的流量限制,求网络最大流即可

  1. 从 源点 向 点1的左点 建一条 容量为$inf$ 的边
  2. 从 点1的左点 向 点1的右点 建一条 容量为$inf$ 的边
  3. 若$\mathtt{f[n]==S}$则从 点n的左点 向 点n的右点 建一条 容量为$inf$ 的边
  4. 若$\mathtt{f[n]==S}$则从 点n的右点 向 汇点 建一条 容量为$inf$ 的边

注意判断当$n==1$时的情况(第三问答案会出现$inf$)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <bits/stdc++.h>
using namespace std;

inline int read() {
int x = 0; int f = 1; char ch = getchar();
while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
while (isdigit(ch)) {x = x * 10 + ch - 48; ch = getchar();}
return x * f;
}

const int maxn = 2010;
const int inf = 0x3f3f3f3f;

int s, t, d[maxn], cur[maxn];

struct Edge {
int from, to, cap, flow;
};
vector<Edge> edges;
vector<int> G[maxn];
void add(int from, int to, int cap) {
edges.push_back((Edge) {from, to, cap, 0});
edges.push_back((Edge) {to, from, 0, 0});
int mm = edges.size();
G[from].push_back(mm - 2);
G[to].push_back(mm - 1);
}

bool vis[maxn];
bool BFS() {
memset(vis, 0, sizeof(vis));
queue<int> Q;
Q.push(s);
d[s] = 0;
vis[s] = 1;
while (!Q.empty()) {
int x = Q.front(); Q.pop();
for (int i = 0; i < G[x].size(); ++i) {
Edge& e = edges[G[x][i]];
if (!vis[e.to] && e.cap > e.flow) {
vis[e.to] = 1;
d[e.to] = d[x] + 1;
Q.push(e.to);
}
}
}
return vis[t];
}

int DFS(int x, int a) {
if (x == t || a == 0) return a;
int flow = 0, f;
for (int& i = cur[x]; i < G[x].size(); ++i) {
Edge& e = edges[G[x][i]];
if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) {
e.flow += f;
edges[G[x][i] ^ 1].flow -= f;
flow += f;
a -= f;
if (a == 0) break;
}
}
return flow;
}

int dinic(int s, int t) {
int flow = 0;
while (BFS()) {
memset(cur, 0, sizeof(cur));
flow += DFS(s, inf);
}
return flow;
}

int n, num[510], dp[510], ans1, ans2, ans3;

int main() {
n = read();
for (int i = 1; i <= n; ++i) {
num[i] = read();
}

// Question 1
for (int i = 1; i <= n; ++i) {
for (int j = 1; j < i; ++j) {
if (num[j] <= num[i] && dp[j] > dp[i]) dp[i] = dp[j];
}
dp[i]++;
ans1 = max(ans1, dp[i]);
}
printf("%d\n", ans1);

// Question 2
s = 0, t = 2 * n + 1;
for (int i = 1; i <= n; ++i) if (dp[i] == 1) add(s, i, 1);
for (int i = 1; i <= n; ++i) add(i, i + n, 1);
for (int i = 1; i <= n; ++i) if (dp[i] == ans1) add (i + n, t, 1);
for (int i = 1; i <= n; ++i)
for (int j = 1; j < i; ++j)
if (num[j] <= num[i] && dp[i] == dp[j] + 1)
add(j + n, i, 1);
ans2 = dinic(s, t);
printf("%d\n", ans2);

// Question 3
if (n == 1) {
printf("1\n");
return 0;
}
add(s, 1, inf); add(1, 1 + n, inf);
if (dp[n] == ans1) {
add(n, n + n, inf);
add(n + n, t, inf);
}
ans3 = ans2 + dinic(s, t);
printf("%d\n", ans3);

return 0;
}

「网络流24题」最长不下降子序列问题-题解

https://blog.tonycrane.cc/p/a66cf8af.html

作者

TonyCrane

发布于

2020-04-15

更新于

2020-05-05

许可协议