「网络流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$)

代码

#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;
}