🪴 Edwin Aze's Blog

最近文章

最近笔记

拯救大兵瑞恩

7分钟阅读

多层图 T3 #6121. 「网络流 24 题」孤岛营救 - 题目 - LibreOJ (loj.ac)

题目描述

1944 年，特种兵麦克接到国防部的命令，要求立即赶赴太平洋上的一个孤岛，营救被敌军俘虏的大兵瑞恩。瑞恩被关押在一个迷宫里，迷宫地形复杂，但幸好麦克得到了迷宫的地形图。迷宫的外形是一个长方形，其南北方向被划分为  行，东西方向被划分为  列， 于是整个迷宫被划分为  个单元。每一个单元的位置可用一个有序数对 (单元的行号, 单元的列号) 来表示。南北或东西方向相邻的  个单元之间可能互通，也可能有一扇锁着的门，或者是一堵不可逾越的墙。迷宫中有一些单元存放着钥匙，并且所有的门被分成  类， 打开同一类的门的钥匙相同，不同类门的钥匙不同。

大兵瑞恩被关押在迷宫的东南角，即  单元里，并已经昏迷。迷宫只有一个入口， 在西北角。也就是说，麦克可以直接进入  单元。另外，麦克从一个单元移动到另一个 相邻单元的时间为 ，拿取所在单元的钥匙的时间以及用钥匙开门的时间可忽略不计。

试设计一个算法，帮助麦克以最快的方式到达瑞恩所在单元，营救大兵瑞恩。

输入格式

第一行有三个整数,分别表示  的值。
第二行是一个整数，表示迷宫中门和墙的总数。
第  行 ，有  个整数，依次为  :当  时，表示  单元与  单元之间有一扇第  类的门，当  时， 表示  单元与  单元之间有一堵不可逾越的墙。
第  行是一个整数 ，表示迷宫中存放的钥匙总数。
第 行  ，有  个整数，依次为 ，表示第  把钥匙存放在  单元里，并且第  把钥匙是用来开启第  类门。
输入数据中同一行各相邻整数之间用一个空格分隔。

输出格式

输出麦克营救到大兵瑞恩的最短时间。如果问题无解，则输出 。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

样例

输入

4 4 9
9
1 2 1 3 2
1 2 2 2 0
2 1 2 2 0
2 1 3 1 0
2 3 3 3 0
2 4 3 4 1
3 2 3 3 0
3 3 4 3 0
4 3 4 4 0
2
2 1 2
4 2 1

输出

14

数据范围与提示

思路

如果还按照最短路中 走到第i个点的最短路径来考虑, 是没法知道当前是否有钥匙的。可以增加一维, 位置相同但此时拥有钥匙数量不同的情况算作不同的点, 最后求一遍最短路即可。 增加点后可以发现, 如果在当前点不动, 只捡钥匙的话, 不会耗时, 故该边权值为0, 其余走一格后的边权值为1, 既然是01图, 就可以用BFS双端队列来求解。

钥匙数就用二进制状态压缩。

代码

#define S second
#define F first
#define pb push_back
#define pf push_front
#define mem(x, n) memset(x, n, sizeof x)
#include <iostream>
#include <cstring>
#include <set>
#include <deque>
using namespace std;
typedef pair<int, int> PII;
// #define debug
typedef long long LL;
 
// using i64 = long long;
const int N = 110, M = 3e4;
int h[N], e[M], w[M], ne[M], idx;
int n, m, p;
int g[11][11];
int key[N];
int dist[N][1 << 10];
bool st[N][1 << 10];
 
void add(int a, int b, int c)
{
  e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
 
int bfs()
{
  deque<PII> q;
  mem(dist, 0x3f);
  q.push_front({g[1][1], 0});
  dist[1][0] = 0;
  while (q.size())
  {
    auto t = q.front();
    q.pop_front();
    int ver = t.F, keys = t.S;
    if (st[ver][keys])
      continue;
    st[ver][keys] = true;
    if (ver == g[n][m])
      return dist[ver][keys];
    if (key[ver])
    {
      int state = keys | key[ver];
      if (dist[ver][state] > dist[ver][keys])
      {
        dist[ver][state] = dist[ver][keys];
        q.push_front({ver, state});
      }
    }
 
    for (int i = h[ver]; ~i; i = ne[i])
    {
      int j = e[i];
      if (w[i] && !((keys >> (w[i] - 1)) & 1))
        continue;
      if (dist[j][keys] > dist[ver][keys] + 1)
      {
        dist[j][keys] = dist[ver][keys] + 1;
        q.push_back({j, keys});
      }
    }
  }
  return -1;
}
 
set<PII> Set;
void build()
{
  int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
    {
      for (int k = 0; k < 4; k++)
      {
        int a = i + dx[k], b = j + dy[k];
        if (a < 1 || a > n || b < 1 || b > m)
          continue;
        if (Set.count({g[i][j], g[a][b]}))
          continue;
        add(g[i][j], g[a][b], 0);
      }
    }
}
 
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
 
  while (cin >> n >> m >> p)
  {
    for (int i = 1, k = 1; i <= n; i++)
      for (int j = 1; j <= m; j++, k++)
        g[i][j] = k;
    mem(h, -1);
    int k;
    cin >> k;
    while (k--)
    {
      int x1, y1, x2, y2, c;
      cin >> x1 >> y1 >> x2 >> y2 >> c;
      int a = g[x1][y1], b = g[x2][y2];
      Set.insert({a, b});
      Set.insert({b, a});
      if (c)
        add(a, b, c), add(b, a, c);
    }
    build();
    int s;
    cin >> s;
    while (s--)
    {
      int a, b, c;
      cin >> a >> b >> c;
      a = g[a][b];
      key[a] |= 1 << (c - 1);
    }
    cout << bfs() << endl;
  }
  return 0;
}

反向链接