Luogu 3645 [APIO 2015] 雅加达的摩天楼

传送门

思路

  唉，我太弱了，我都看出来要分块了，就是做不来。不过终于把题读对了。

  先来看子任务三怎么做。显然可以有一个 O(m2) O ( m 2 ) $O(m^2)$ 的连边，然后直接跑最短路就可以了。但是分好少啊 QAQ，所以我们来看子任务四。我们将在同一个位置的 doge 构成一个零环，然后只向不在同一个位置的 doge 连边，且对于每个位置最多只连接一次边。这样的时间复杂度就是 O(nm) O ( n m ) $O(nm)$ 的了。

  注意，连边只能是 doge 连 doge，不能在位置上跳着跳着连。例如，如果非要把位置作为结点，则只能连 1→3 1 → 3 $1 \to 3$， 1→5 1 → 5 $1 \to 5$（注意还要加上边权），不能连两条边权为 1 1 $1$ 的 1→3$1\to 3$$1 \to 3$， 3→5 3 → 5 $3 \to 5$。（想一想，为什么）

正解

  我们可以拆点。我们令位置为结点，对于每个位置，我们把它拆成 k+1 k + 1 $k + 1$ 个结点，其中 k k $k$ 为参数。对于被拆的点，我们从 0$0$$0$ 开始编号， 0 0 $0$ 号点表示位置本身，i(i>0)$i(i>0)$$i \pod {i > 0}$ 号点表示“ i i $i$ 步快速通道”，即向左右的 i$i$$i$ 步快速通道连一条边权为 1 1 $1$ 的边。

  如上图，如果某个位置有一个跳跃能力为 k$k$$k$ 的 doge，我们就从那个位置的 0 0 $0$ 号点向 k$k$$k$ 步快速通道连一条边权为 0 0 $0$ 的有向边。另外，我们要保证能够从快速通道回到原结点，所以所有快速通道都要向原结点连一条边权为 0$0$$0$ 的有向边。

  其实，这个做法与其叫拆点，不如叫拆边：

  显然这么做会有 O(nk) O ( n k ) $O(nk)$ 个结点，多出 O(nk) O ( n k ) $O(nk)$ 条边，因此 k k $k$ 不能太大，也不能太小。对于跳跃能力小于 k$k$$k$ 的情况，我们选择建立快速通道，额外时间复杂度为 O(1) O ( 1 ) $O(1)$；对于剩下的我们暴力建边，额外时间复杂度 O(nk) O ( n k ) $O(\frac {n} {k})$。我们不妨令 nk=nm2k n k = n m 2 k $nk = \frac {n \frac {m} {2}} {k}$，解得 k=m2−−√ k = m 2 $k = \sqrt \frac {m} {2}$，即理论上让 k=120 k = 120 $k = 120$ 左右就好了，实际上由于每只 doge 跳跃能力的不确定（我这里假设两种情况五五开）， k k $k$ 到底等于多少才好需要调参。

参考代码

  由于边数很多，所以我们直接判断就好了，无需手动建图。

  另外，上面的参数已经能够满足要求了。调成 m4−−√$\sqrt{\frac{m}{4}}$$\sqrt \frac {m} {4}$ 更快。

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef int INT_PUT;
INT_PUT readIn()
{
    INT_PUT a = 0; bool positive = true;
    char ch = getchar();
    while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
    if (ch == '-') { positive = false; ch = getchar(); }
    while (std::isdigit(ch)) { a = a * 10 - (ch - '0'); ch = getchar(); }
    return positive ? -a : a;
}
void printOut(INT_PUT x)
{
    char buffer[20]; int length = 0;
    if (x < 0) putchar('-'); else x = -x;
    do buffer[length++] = -(x % 10) + '0'; while (x /= 10);
    do putchar(buffer[--length]); while (length);
}

int INF;
const int maxn = 30005;
int n, m;

#define RunInstance(x) delete new x
struct work
{
    static const int maxk = 90;
    int k;
    std::vector<std::vector<int> > appear;
    std::vector<std::vector<int> > fast;
    std::vector<std::vector<int> > slow;
    int pos[maxn];
    int val[maxn];

    static const int size = maxn * maxk;
    int dis[size];
    bool inQ[size];
    int q[size];
    int head, tail;

    void slack(int from, int to, int cost)
    {
        if (dis[from] + cost < dis[to])
        {
            dis[to] = dis[from] + cost;
            if (!inQ[to])
            {
                q[tail] = to;
                tail = tail + 1 == size ? 0 : tail + 1;
                inQ[to] = true;
            }
        }
    }

    void SPFA()
    {
        head = tail = 0;
        memset(dis, 0x3f, sizeof(dis));
        memset(inQ, 0, sizeof(inQ));
        dis[pos[0]] = 0;
        q[tail++] = pos[0];
        inQ[pos[0]] = true;
        while (head != tail)
        {
            int from = q[head];
            inQ[from] = false;
            head = head + 1 == size ? 0 : head + 1;
            if (from >= n)
            {
                int way = from / n;
                int idx = from - way * n;
                int to;
                if (idx - way >= 0)
                    slack(from, from - way, 1);
                if (idx + way < n)
                    slack(from, from + way, 1);
                slack(from, idx, 0);
            }
            else
            {
                for (int i = 0; i < fast[from].size(); i++)
                    slack(from, from + n * fast[from][i], 0);
                for (int i = 0; i < slow[from].size(); i++)
                {
                    register int cnt;
                    register int step = slow[from][i];
                    register int cost;
                    cnt = from - step;
                    cost = 1;
                    while (cnt >= 0)
                    {
                        slack(from, cnt, cost);
                        cnt -= step;
                        cost++;
                    }
                    cnt = from + step;
                    cost = 1;
                    while (cnt < n)
                    {
                        slack(from, cnt, cost);
                        cnt += step;
                        cost++;
                    }
                }
            }
        }
    }

    work() : dis(), inQ()
    {
        k = std::sqrt(m / 4);
        appear.resize(n);
        fast.resize(n);
        slow.resize(n);
        for (int i = 0; i < m; i++)
        {
            pos[i] = readIn();
            val[i] = readIn();
            appear[pos[i]].push_back(i);
            if (val[i] <= k) fast[pos[i]].push_back(val[i]);
            else slow[pos[i]].push_back(val[i]);
        }
        for (int i = 0; i < n; i++)
        {
            std::sort(fast[i].begin(), fast[i].end());
            fast[i].resize(std::unique(fast[i].begin(), fast[i].end()) - fast[i].begin());
            std::sort(slow[i].begin(), slow[i].end());
            slow[i].resize(std::unique(slow[i].begin(), slow[i].end()) - slow[i].begin());
        }

        SPFA();
        if (dis[pos[1]] >= INF)
            printOut(-1);
        else
            printOut(dis[pos[1]]);
    }
};

void run()
{
    memset(&INF, 0x3f, sizeof(INF));
    n = readIn();
    m = readIn();
    RunInstance(work);
}

int main()
{
    run();
    return 0;
}

Update

  好像这是个 01 BFS……你懂的……