Luogu 3638 [APIO 2013] 机器人

2023-05-16

- - - - 传送门
      - 思路
      - 正解
      - 参考代码
      - 关于 SPFA

传送门

思路

$n$ 这么小，会不会是搜索题？稍有经验的我直接否定了这个结论 = =。仔细读题并分析样例，发现原来一个位置可以有多个机器人，且机器人行走的时候无视其它机器人，那这个就是一张图啊。可以将这张图预处理出来，则问题变为把所有机器人在某个结点合并的路径长度之和的最小值。

我本以为跑个多源 BFS 就好了，但是猛然发现机器人合并后步数会改变，然后我就凉了……

正解

还是先将整张图预处理出来，注意需要用 DFS 记忆化保证时间复杂度。

这道题其实是一个动态规划（怎么想到的 = =）。我们设 $f_{l, r, x, y}$ 表示使得 $l \sim r$ 的复合机器人在 $(x, y)$ 的最小代价，显然边界条件为：

fi,i,xi,yi=0 f i , i , x i , y i = 0

$f_{i, i, x_i, y_i} = 0$

考虑转移。显然我们可以选择走一步：

fl,k,x,y+fk+1,r,x,y→fl,r,x,y f l , k , x , y + f k + 1 , r , x , y → f l , r , x , y

$f_{l, k, x, y} + f_{k + 1, r, x, y} \to f_{l, r, x, y}$

fl,r,x,y+1→fl,r,x′,y′ f l , r , x , y + 1 → f l , r , x ′ , y ′

$f_{l, r, x, y} + 1 \to f_{l, r, x', y'}$

对于一个位置，我们先用第一个转移计算出自己的最小代价，再用第二个转移去更新别人的最小代价。发现，这个转移的方法与斯坦纳树的做法是十分类似的，但是和斯坦纳树本身毛关系都没有。

祸害众生的神仙题解

始作俑者，害得看透这道题的人偏偏也加上了一个斯坦纳树的标签

是个铲铲！

参考代码

唉，我太弱了，什么都不会，DFS 一开始写错了，调了一个上午……

（C++ 11 is needed）

#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>
#define loop register int
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 = 505;
int n, w, h;
int rect[maxn][maxn];
typedef std::pair<int, int> Point;
Point pos[10];

enum { RIGHT, UP, LEFT, DOWN };
const int vecx[] = { 0, -1, 0, 1 };
const int vecy[] = { 1, 0, -1, 0 };
Point to[maxn][maxn][4];

int vis[maxn][maxn][4];
int stamp;
void DFS(int x, int y, int dir)
{
    if (to[x][y][dir].first)
        return;
    vis[x][y][dir] = stamp;
    int newz = dir;
    if (rect[x][y] == -2)
        newz = (newz + 1) & 3;
    else if (rect[x][y] == -3)
        newz = (newz + 4 - 1) & 3;
    int newx = x + vecx[newz];
    int newy = y + vecy[newz];
    if (!(1 <= newx && newx <= h && 1 <= newy && newy <= w) || rect[newx][newy] == -1)
    {
        to[x][y][dir] = std::make_pair(x, y);
        return;
    }
    else if (vis[newx][newy][newz] == stamp)
    {
        to[x][y][dir] = std::make_pair(-1, -1);
        return;
    }
    DFS(newx, newy, newz);
    to[x][y][dir] = to[newx][newy][newz];
}
void init()
{
    for (loop x = 1; x <= h; x++)
        for (loop y = 1; y <= w; y++)
            for (loop i = 0; i < 4; i++)
            {
                stamp++;
                DFS(x, y, i);
            }
}

int f[10][10][maxn][maxn];
struct Queue
{
    Point c[maxn * maxn];
    int head, tail;
    Queue() { clear(); }
    void clear() { head = tail = 0; }
    void push(const Point& x) { c[tail++] = x; }
    void pop() { head++; }
    Point front() { return c[head]; }
    int val(int l, int r) { return f[l][r][c[head].first][c[head].second]; }
    bool empty() { return head == tail; }
    void sort(int l, int r)
    {
        std::sort(c + head, c + tail,
            [=](const Point& a, const Point& b)
        {
            return f[l][r][a.first][a.second] < f[l][r][b.first][b.second];
        });
    }
} q1, q2;
bool inQ[maxn * maxn];
void SPFA(int l, int r)
{
    q1.clear();
    q2.clear();
    for (loop x = 1; x <= h; x++)
        for (loop y = 1; y <= w; y++)
            if (f[l][r][x][y] < INF)
            {
                q1.push(std::make_pair(x, y));
                inQ[x * w + y] = true;
            }
    q1.sort(l, r);

    while (!(q1.empty() && q2.empty()))
    {
        Point from;
        if (q2.empty() || (!q1.empty() && q1.val(l, r) <= q2.val(l, r)))
        {
            from = q1.front();
            q1.pop();
        }
        else
        {
            from = q2.front();
            q2.pop();
        }
        inQ[from.first * w + from.second] = false;

        for (int i = 0; i < 4; i++)
        {
            const Point& t = to[from.first][from.second][i];
            if (t.first == -1) continue;
            int update = f[l][r][from.first][from.second] + 1;
            int& ans = f[l][r][t.first][t.second];
            if (update < ans)
            {
                ans = update;
                if (!inQ[t.first * w + t.second])
                {
                    q2.push(std::make_pair(t.first, t.second));
                    inQ[t.first * w + t.second] = true;
                }
            }
        }
    }
}
void solve()
{
    memset(f, 0x3f, sizeof(f));
    for (int i = 1; i <= n; i++)
        f[i][i][pos[i].first][pos[i].second] = 0;

    for (int len = 1; len <= n; len++)
    {
        for (int l = 1, r = l + len - 1; r <= n; l++, r++)
        {
            if (len > 1)
                for (loop x = 1; x <= h; x++)
                    for (loop y = 1; y <= w; y++)
                        for (loop i = l; i < r; i++)
                            f[l][r][x][y] = std::min(f[l][r][x][y], f[l][i][x][y] + f[i + 1][r][x][y]);

            SPFA(l, r);
        }
    }

    int ans = INF;
    for (int i = 1; i <= h; i++)
        for (int j = 1; j <= w; j++)
            ans = std::min(ans, f[1][n][i][j]);
    if (ans >= INF)
        printOut(-1);
    else
        printOut(ans);
}

void run()
{
    memset(&INF, 0x3f, sizeof(INF));
    n = readIn();
    w = readIn();
    h = readIn();
    for (int x = 1; x <= h; x++)
    {
        for (int y = 1; y <= w; y++)
        {
            char ch = getchar();
            while (!(std::isdigit(ch) || ch == '.' ||
                ch == 'x' || ch == 'A' || ch == 'C'))
                ch = getchar();
            switch (ch)
            {
            case 'x': rect[x][y] = -1; break;
            case 'A': rect[x][y] = -2; break;
            case 'C': rect[x][y] = -3; break;
            case '.': break;
            default: pos[ch - '0'] = std::make_pair(x, y);
            }
        }
    }

    init();
    solve();
}

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

关于 SPFA

这道题我使用两个队列进行 SPFA 而不是一个，同时一开始还排了序，这是因为这样使得这个算法满足 BFS 的性质，即更新后的点不会再次被更新。这意味着时间复杂度为 $O(n + m)$ 。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

luogu

3638

APIO

2013