luoguP2304 [NOI2015] 小园丁与老司机

啊对对对……

小园丁与老司机

老司机的时间

关于最长路，显然 dp ，我们发现是没有向下的，而且数据也提示我们把 $y_i$ 作为 dp 的阶段，令 d[i] 表示到点 $(x_i, y_i)$ 的最长长度，明显， $d[i]$ 由 $(x_i, y_i)$ 左、右、左下、右下和正下方的点转移，由于以 $y_i$ 为阶段，左下、右下和正下方的点是已知的（可以预处理出每个点向上转移到那里），但左右的点可以互相转移，顺序未知，考虑高斯消元，但高斯他这次不靠谱了，因为方程里有个 $\max$ ，那……我们就只好枚举每层（ $y_i$ 相等的点为一层）的 dp 顺序，这不爆炸？

看题解 发现，我们走的一定是一段连续的区间，如图，若我们从点 $A$ 进入该层，从点 $B$ 离开，会发现射线 $BA$ 上的点我们都可达，而 $B$ 另一侧的点都不可达（这是因为只能去往最近的未到过的点，如果我们取了 $B$ 另一侧的点，说明我们一定到过了 $B$ ，那就不可能再回到 $B$ 了）

所以，我们对每一层，把该层的点按 $x_i$ 升序排序，然后处理出前/后缀？这样确实可以 dp 了，设 $d[i]$ 表示“以点 $(x_i, y_i)$ 作为它所在层的出点（即上图的点 $B$ ）的最长路长度”，计算时先枚举层数（可以把点排序来做到按层数转移），把本层从下面转移的全都转移了，再考虑本层的情况，但，难打的和……一样

我们再 瞟一眼题解 思考一下，发现可以拆点，把射线向左/右分开，更具体地，我们把一个点分成三个：左、右、上，分别代表从这个点向左走、向右走、向上走（都是必须走），如图：

黑色是向上点（你会发现所有点最后都走到一个黑色点，因为只有黑色点会连出向上一层的边）；红色是左向，蓝色是右向；所有横向走的边权都为 $1$ ，代表每走一次就多取了一个点；纵向的边权为 $0$ ，代表同一个点的不同状态

以上上幅图的 $A$ 进 $B$ 出为例，设 $A$ 是 $4$ 号点， $B$ 是 $2$ 号点，我们从 $A$ 到 $B$ 的路径就是 $下层 \to 红3 \to 红2 \to 黑2 \to 上层$ ，这里我们会发现 $4$ 号点及右边的 $5$ 号点没算，所以我们把 $红3$ 的入边的权值设为 $3$ （因为只要从 $红4$ 入，就意味着必须从左边某个点出，所以不连 $4$ ，直接连向 $3$ ，那么 $4, 5$ 号是必定可达的）

这里有一个要注意的地方，从起点开始就可以横着走到 $(x, 0)$ ，所以 dp 的起点是原点的 $红、蓝、黑$ 三个点

用以上方法，我们可以建出一个点数为 $3n$ 的 DAG ，直接在上面 dp 即可，比预处前/后缀简单（但也没简单多少，这道题就跟……一样），还有一个问题是要求方案（园丁的题也要用），记录来向即可

小园丁的时间

我们把向上的黑点记作 $U$ ，向左、右的分别记作 $L, R$ ，明显，不合法的边是最长路上从 $U$ 型点上出发的所有边

我们新建一张图，初始只有 $n$ 个点，我们把所有可以在最长路上的边加入图中，上界为 $+ \infty$ ，下界为 $1$ ；然后从源点向每个点连边、从每个点向汇点连边，都是上界为 $+ \infty$ ，下界为 $0$ 的边，跑一遍源汇上下界最小流即可

这图有个特殊性质：一定有解，所以可以直接把可行流的部分省略（因为一定可行），只跑最小流

调试

打了好久，第一次交， TLE + WA $45 pts$ 呃呃呃，发现有一部分 WA 好像是网络流建图的问题，我把 dad(i, T, -ve[i]) 打错为 dad(i, T, ve[i]) ，好吧，我就承认我是个伞兵好吗

改了以后是 TLE + WA $75 pts$ ，WA 好像是 dp 挂了，先不管，搞搞 TLE，发现时间复杂度为 $O(Dinic)$ ，尝试改为 HLPP ，结果 RE ，然后尝试吸氧 + Dinic，也 RE ，怀疑是建图挂了

决定先把那个 WA 搞了，（臭不要脸的交空代码骗数据）发现 WA 的点是最长路很长（接近 $N$ ）且最优路线不唯一的点，感觉是太长了 dp 挂掉了，仔细一想，我用 vector 记录了所有的方案，中间一条边会被记录多次，那谁知道空间怎么样了，于是考虑只记录一条来向用于回答第老司机，其它的最长路用在反向图上 dfs 解决，另外，边一定要开足够大！

然后……TLE $75 pts$ ，我觉得网络流不该 fake ，应该还是老司机的问题，于是下了一组数据，发现我建图的 dfs 没判重！每个点被重复到达了很多次，感觉自己被老司机算计的明明白白

代码

#include <bits/stdc++.h>
#define fi first
#define se second
#define STC static
#define L(x) (x)
#define R(x) (x + n)
#define U(x) (x + 2 * n)
#define mem(x, y) memset(x, y, sizeof x)
using PII = std::pair<int, int>;
const int N = 5e4 + 100, INF = 0x3f3f3f3f, M = 5e6 + 5;
int n, to[N][5];
PII a[N]; //(fi,se)=(x,y)
namespace DP
{
    struct Edge{ int ne, ver, w; } e[M], eb[M]; //边开足够大
    int h[N * 3], idx = 0, hb[N * 3], idb = 0, nn, d[N * 3], ans = -INF, from[N * 3], vis[N * 3];
    void add(int x, int y, int z){ e[idx] = {h[x], y, z}, h[x] = idx++, eb[idb] = {hb[y], x, z}, hb[y] = idb++; }
    std::vector<PII> longway;
    PII get(int x){ return x <= n ? PII(x, 0) : (x <= 2 * n ? PII(x - n, 1) : PII(x - 2 * n, 2)); }
    void get_to()
    {
        using Three = std::pair<PII, int>;
        std::vector<Three> b; //桶,(fi,se.fi, se.se)=(bid,val,id)
        b.push_back(Three({-INF, -INF}, -INF));
        //向上
        for (int i = 1; i <= n; ++i) b.push_back(Three(a[i], i));
        std::sort(b.begin(), b.end());
        for (int i = 1; i < n; ++i) if (b[i + 1].fi.fi == b[i].fi.fi) to[b[i].se][0] = b[i + 1].se;
        b.clear(), b.push_back(Three({-INF, -INF}, -INF));
        //左上
        for (int i = 1; i <= n; ++i) b.push_back(Three({a[i].fi + a[i].se, a[i].se}, i));
        std::sort(b.begin(), b.end());
        for (int i = 1; i < n; ++i) if (b[i + 1].fi.fi == b[i].fi.fi) to[b[i].se][1] = b[i + 1].se;
        b.clear(), b.push_back(Three({-INF, -INF}, -INF));
        //右上
        for (int i = 1; i <= n; ++i) b.push_back(Three({a[i].se - a[i].fi, a[i].se}, i));
        std::sort(b.begin(), b.end());
        for (int i = 1; i < n; ++i) if (b[i + 1].fi.fi == b[i].fi.fi) to[b[i].se][2] = b[i + 1].se;
        b.clear(), b.push_back(Three({-INF, -INF}, -INF));
        //向右和向左
        for (int i = 1; i <= n; ++i) b.push_back(Three({a[i].se, a[i].fi}, i));
        std::sort(b.begin(), b.end());
        for (int i = 1; i < n; ++i) if (b[i + 1].fi.fi == b[i].fi.fi) to[b[i].se][3] = b[i + 1].se, to[b[i + 1].se][4] = b[i].se;
    }
    void build()
    {
        STC int t[N][2]; //辅助计算上行边的权值
        mem(h, -1), mem(hb, -1);
        get_to(); //找到每个点能到那个点
        for (int i = 1; i <= n; ++i)
        {
            add(R(i), U(i), 0), add(L(i), U(i), 0);
            if (to[i][3]) add(R(i), R(to[i][3]), 1);
            else for (int j = i, k = 1; j; j = to[j][4], ++k) t[j][0] = k; //右端点向左
            if (to[i][4]) add(L(i), L(to[i][4]), 1);
            else for (int j = i, k = 1; j; j = to[j][3], ++k) t[j][1] = k; //左端点向右
        }
        for (int i = 1; i <= n; ++i)
            for (int j = 0; j <= 2; ++j) if (to[i][j])
            {
                if (to[to[i][j]][3]) add(U(i), R(to[to[i][j]][3]), t[to[i][j]][1] + 1); //注意下标不要混
                if (to[to[i][j]][4]) add(U(i), L(to[to[i][j]][4]), t[to[i][j]][0] + 1);
                add(U(i), U(to[i][j]), 1);
            }
    }
    void topu()
    {
        STC int du[N * 3];
        std::queue<int> q;
        mem(d, 0xcf); //是-INF
        for (int i = 0; i < idx; ++i) ++du[e[i].ver];
        du[U(n)] = d[U(n)] = du[R(n)] = d[R(n)] = du[L(n)] = d[L(n)] = 0;
        for (int i = 1; i <= nn; ++i) if (!du[i]) q.push(i);
        while (!q.empty())
        {
            int x = q.front(); q.pop();
            for (int i = h[x], y; ~i; i = e[i].ne)
            {
                if (d[y = e[i].ver] < d[x] + e[i].w)
                {
                    d[y] = d[x] + e[i].w;
                    from[y] = x;
                }
                if ((--du[y]) == 0) q.push(y);
            }
        }
    }
    void work()
    {
        nn = n * 3;
        build(), topu();
        //回答前两个询问
        STC int stk[N], top = 0;
        for (int i = 1; i <= n; ++i) ans = std::max(ans, d[U(i)]);
        printf("%d\n", ans);
        for (int x = 1, y; x <= n; ++x) if (d[U(x)] == ans)
        {
            for (x = U(x), stk[++top] = x; from[x]; stk[++top] = x) x = from[x]; 
            for (PII t = get(stk[top--]), lt; top;)
            {
                lt = t, t = get(stk[top--]);
                if (lt.se == t.se) printf("%d ", t.fi);
                else if (t.se == 0)
                {
                    for (y = to[t.fi][3]; y; y = to[y][3]) printf("%d ", y);
                    printf("%d ", t.fi);
                }
                else if (t.se == 1) 
                {
                    for (y = to[t.fi][4]; y; y = to[y][4]) printf("%d ", y);
                    printf("%d ", t.fi);
                }
            }
            puts("");
            break;
        }
    }
    //下面的函数找出最长路,Dinic建边用
    void dfs(int y)
    {
        for (int i = hb[y], x; ~i; i = eb[i].ne) if (d[x = eb[i].ver] + eb[i].w == d[y])
        {
            PII ty = get(y), tx = get(x);
            if (tx.se == 2)
                for (int j = 0, tt; j <= 2; ++j) if (tt = to[tx.fi][j])
                {
                    if (ty.fi == to[tt][3] && ty.se == 1) longway.push_back({tx.fi, tt});
                    if (ty.fi == to[tt][4] && ty.se == 0) longway.push_back({tx.fi, tt});
                    if (ty.fi == tt && ty.se == 2) longway.push_back({tx.fi, tt});
                }
            if (vis[x]) continue; //不加会TLE
            vis[x] = true, dfs(x);
        }
    }
    void find(){ for (int i = 1; i <= n; ++i) if (d[U(i)] == ans && (vis[U(i)] = true)) dfs(U(i)); }
}
namespace Dinic
{
    struct Edge{int ne, ver, w; } e[M]; //我也不知道边开多大
    int h[N], idx = 0, S, T, ans, cur[N], dep[N];
    void add(int x, int y, int z){ e[idx] = {h[x], y, z}, h[x] = idx++; }
    void dad(int x, int y, int z){ add(x, y, z), add(y, x, 0); }
    void build()
    {
        using DP::longway;
        DP::find(); //找到最长路
        STC int ve[N];
        mem(h, -1);
        S = n + 1, T = S + 1;
        sort(longway.begin(), longway.end());
        longway.erase(std::unique(longway.begin(), longway.end()), longway.end()); //去重边
        for (PII lw : longway) dad(lw.fi, lw.se, INF), --ve[lw.fi], ++ve[lw.se];
        for (int i = 1; i <= n; ++i)
            if (ve[i] > 0) dad(S, i, ve[i]), ans += ve[i]; //一定有解
            else if (ve[i] < 0) dad(i, T, -ve[i]);
    }
    bool bfs()
    {
        mem(dep, -1);
        std::queue<int> q;
        for (q.push(S), dep[S] = 0, cur[S] = h[S]; !q.empty(); )
        {
            int x = q.front(); q.pop();
            for (int i = h[x], y; ~i; i = e[i].ne) if (dep[y = e[i].ver] == -1 && e[i].w)
            {
                cur[y] = h[y], dep[y] = dep[x] + 1;
                if (y == T) return true;
                q.push(y);
            }
        }
        return false;
    }
    int find(int x, int lim)
    {
        if (x == T) return lim;
        int flow = 0, t, y;
        for (int i = cur[x]; ~i && flow < lim; i = e[i].ne)
        {
            cur[x] = i;
            if (dep[y = e[i].ver] == dep[x] + 1 && e[i].w)
            {
                if (!(t = find(y, std::min(e[i].w, lim - flow)))) dep[y] = -1;
                e[i].w -= t, e[i ^ 1].w += t, flow += t;
            }
        }
        return flow;
    }
    int dinic()
    {
        int res = 0, flow;
        while (bfs()) while (flow = find(S, INF)) res += flow;
        return res;
    }
    void work(){ build(), printf("%d\n", ans - dinic()); }
}

int main()
{
    scanf("%d", &n), a[++n] = {0, 0}; //把原点也看作一棵树
    for (int i = 1; i <= n; ++i) scanf("%d %d", &a[i].fi, &a[i].se);
    DP::work(), Dinic::work(); 
    return 0;
}