[数据结构与算法]P2766 Dinic

题意

传送门 P2766 最长不下降子序列问题

题解

最长不下降子序列的长度 DP 求解即可。$d{p}_i$ 代表 $i$ 为初始元素的最长不下降子序列长度。 d p i = max ? i < j , x i ≤ x j { d p j } + 1 dp_i = \max_{i<j,x_i\leq x_j} \{dp_j\}+1 dpi?=maxi<j,xi?≤xj??{dpj?}+1。

对于第二问，由于子序列长度 $len$ 是可达的最大长度，那么子序列第 $k$ 个元素只可能是 $d{p}_i=len?k+1$ 的位置 $i$，否则，可以构造出更长的不下降子序列。那么可以根据分层图的思想建图。为了满足每个元素至多使用一次的约束，将元素 $v$ 拆为入点 $v_{in}$ 与出点 $v_{out}$，$v_{in}\to v_{out}$ 连一条容量为 $1$ 的边。

设源点汇点分别为 $s,t$，则对于 $d{p}_i=len$ 的节点 $s\to v_{in}$，对于 $d{p}_i=1$ 的节点 $v_{out}\to t$，其余节点 $i$ 向可能为其所在子序列下一个元素的节点 $j$ 连一条边。对于第二问而言，这些边的容量大于等于 $1$ 即可。最大流即第二问答案。

对于第三问，首先去掉起始与结尾元素的限制，即对于 $d{p}_i=len$ 或 $d{p}_i=1$ 的节点，在第二问基础上去除使用次数的限制，即 $i_{in}\to i_{out}$ 连一条容量为 $\infty$ 的边。对于元素 $x_i$，其所在不下降子序列中的下一个位置的可能元素 $x_j$ 必然互不相同，否则可以构造出更长的不下降子序列。那么只需要使 $i_{out}\to j_{in}$ 边的容量设置为 $1$。跑 Dinic ，最大流即第三问答案。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
const int MAXN = 505, MAXV = MAXN * 2, INF = 0x3f3f3f3f;
int N, V;
struct edge
{
    int to, cap, rev;
};
vector<edge> G[MAXV];
int iter[MAXV], level[MAXV];

void add_edge(int from, int to, int cap)
{
    G[from].pb({to, cap, G[to].size()});
    G[to].pb({from, 0, G[from].size() - 1});
}

void bfs(int s)
{
    for (int v = 0; v < V; ++v)
        level[v] = -1;
    queue<int> q;
    level[s] = 0;
    q.push(s);
    while (q.size())
    {
        int v = q.front();
        q.pop();
        for (auto &e : G[v])
            if (e.cap > 0 && level[e.to] == -1)
                level[e.to] = level[v] + 1, q.push(e.to);
    }
}

int dfs(int v, int t, int f)
{
    if (v == t)
        return f;
    for (int &i = iter[v]; i < G[v].size(); ++i)
    {
        auto &e = G[v][i];
        if (e.cap > 0 && level[e.to] > level[v])
        {
            int d = dfs(e.to, t, min(f, e.cap));
            if (d > 0)
            {
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

int max_flow(int s, int t)
{
    int flow = 0;
    for (;;)
    {
        bfs(s);
        if (level[t] == -1)
            return flow;
        for (int v = 0; v < V; ++v)
            iter[v] = 0;
        int f;
        while ((f = dfs(s, t, INF)) > 0)
            flow += f;
    }
}

int a[MAXN], dp[MAXN];

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> N;
    for (int i = 0; i < N; ++i)
        cin >> a[i];
    dp[N] = 0, a[N] = INF;
    int len = 0, cnt = 0;
    for (int i = N - 1; i >= 0; --i)
    {
        for (int j = i + 1; j <= N; ++j)
            if (a[i] <= a[j])
                dp[i] = max(dp[i], dp[j] + 1);
        if (dp[i] > len)
            len = dp[i], cnt = 1;
        else if (dp[i] == len)
            ++cnt;
    }
    cout << len << '\n';

    int s = 2 * N, t = s + 1;
    V = t + 1;
    for (int i = 0; i < N; ++i)
    {
        if (dp[i] == len)
            add_edge(s, i, INF);
        if (dp[i] == 1)
            add_edge(N + i, t, INF);
        add_edge(i, N + i, 1);
        for (int j = i + 1; j < N; ++j)
            if (a[i] <= a[j] && dp[i] == dp[j] + 1)
                add_edge(N + i, j, 1);
    }
    int flow = max_flow(s, t);
    cout << flow << '\n';

    if (len == 1)
    {
        cout << cnt << '\n';
        return 0;
    }
    for (int i = 0; i < N; ++i)
    {
        if (dp[i] == len)
            add_edge(i, N + i, INF);
        if (dp[i] == 1)
            add_edge(i, N + i, INF);
    }
    flow += max_flow(s, t);
    cout << flow << '\n';
    return 0;
}