[FJOI2018]所罗门的宝藏

2024-03-04 09:05:53

大概是最后一篇题解，其实只是想颓废一下打个故事

据古代传说记载，所罗门王即是智慧的代表，又是财富的象征。他建立了强大而富有的国家，聚集了大批的黄金象牙和钻石，并把这些价值连城的珍宝藏在一个神秘的地方，这就是万世瞩目的“所罗门的宝藏”。多少个世纪以来，人们一直在寻找这批早已失落的古代文明宝藏，寻找盛产黄金和钻石的宝地。曾经追寻所罗门王宝藏的冒险者们都一去不回，至今没有人解开这个迷题。亨利男爵在一次幸运的旅行中以外地得到了三百年前一本葡萄牙贵族留下的写在羊皮卷上的所罗门王的宝藏图和一本寻宝秘笈。在这张藏宝图的诱惑下，亨利男爵邀请约翰上校和勇敢的猎象人夸特曼开始了寻找埋藏在黑暗地底的所罗门王宝藏的艰险历程。他们横穿渺无边际的沙漠和浓荫蔽日的原始森林，穿越汹涌澎湃的激流险滩，翻越高耸入云的峻岭雪山，饱尝沙漠的酷热和冰雪严寒，在藏宝图的指引下来到了非洲一个原始的神秘国度库库安纳。这里有残酷的人殉制度，有一个拥有一千个妻室的独眼暴君特瓦拉，有像兀鹫一般丑陋诡诈的老而不死的女巫加古尔，还有美丽聪明的绝代佳人弗拉塔。在这片陌生而又险象环生的土地上三位寻宝英雄历尽艰辛。终于在绝代佳人弗拉塔的帮助下在海底深处找到了珍藏这批价值连城宝藏的巨大藏宝洞。然而，在女巫加古尔的精心策划下，一场灭顶之灾正在悄悄逼近。

藏宝洞的洞门十分坚固且洞门紧闭，如果不知道开启洞门的秘密是无法打开藏宝洞的洞门的。在藏宝洞的洞门一侧有一个奇怪的矩形密码阵列。根据寻宝秘笈记载，在密码阵列的每行的左侧和每列的顶端有一颗红宝石按钮。每个按钮都可以向左或向右转动。每向左转动7一次按钮，相应的行或列重点数字都增加一。每次向右转动一次按钮，相应的行或列中的数字都减小一。在矩阵密码列阵的若干个位置镶嵌着绿宝石。只有当所有绿宝石位置的数字与藏宝图记载的密码完全相同，紧闭的洞门才会打开。女巫加古尔早已得知开门的秘密。为了阻止寻宝者打开洞门，女巫加古尔为开门的密码列阵设置了全零的初始状态。试图打开洞门的寻宝者如果不能迅速转动按钮使所有绿宝石上的数字与藏宝图记载的一样，就会启动藏宝洞玄妙的机关，使寻宝者遭到灭顶攻击而死于非命。

您能帮助三位寻宝者顺利打开藏宝洞的洞门吗？

编程任务：对于给出的密码阵列，找到获得正确密码的红宝石按钮转动序列。

输入格式

输入的第一行中有一个正整数T(T≤5) 表示有 T 组数据。每组数据的第一行有 3个正整数 n,m和 k，表示洞门密码阵列共有 n行和 m 列，0<n,m,k ≤ 1000。各行从上到下依次编号为 1,2,……,n；各列从左到右依次编号为 1,2,……,m 。接下来的k 行中每行有三个整数 x,y,c，分别表示第 k 个绿宝石在密码阵列中的位置和密码，x 为行号 y 为列号，c为该位置处的密码。

输出格式

对于每组数据，用一行输出 Yes或者No。输出Yes表示存在获得正确密码的红宝石按钮的转动序列。输出 No则表示无法找到获得正确密码的红宝石按钮的转动序列。

输入输出样例

输入 #1

输出 #1

Yes
No

说明/提示

对于 100%的数据,1 ≤ n, m, k ≤ 1000，k ≤ n * m，∣c∣ ≤ 1000000。

Solution

对于每个绿宝石，将他的横纵坐标连边，则对于每个点加或者减就是相当于对所有相邻的边操作。对于每条边都有del[u] + del[v] == w

如果不满足上式，则不合法

满足的话就更新一下del[v]然后扔进队列去bfs

最后判断一下是不是每个点都合法就好了

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
inline long long read() {
  long long x = 0; int f = 0; char c = getchar();
  while (c < '0' || c > '9') f |= c == '-', c = getchar();
  while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
  return f ? -x : x;
}

int n, m, k, cnt, hd[2005], del[2005];
struct szh {
  int to, nxt, w;
}a[2005];
bool vis[2005];
queue<int> q;
inline void add(int x, int y, int z) {
  a[++cnt].to = y, a[cnt].w = z, a[cnt].nxt = hd[x], hd[x] = cnt;
}
inline bool bfs(int s) {
  while (!q.empty()) q.pop();
  q.push(s); vis[s] = 1;
  while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int i = hd[u], v; v = a[i].to, i; i = a[i].nxt) 
      if (vis[v]) {
        if (del[u] + del[v] != a[i].w) return 0;
      }
      else {
        del[v] = a[i].w - del[u], vis[v] = 1;
        q.push(v); 
      }
  } 
  return 1;
}
int main() {
  int T = read();
  while (T--) {
    memset(vis, 0, sizeof vis);
    memset(hd, 0, sizeof hd);
    cnt = 0;
    n = read(); m = read(); k = read();
    for (int i = 1, x, y, z; i <= k; ++i) {
      x = read(); y = read(); z = read();
      add(x, y + n, z); add(y + n, x, z);
    }
    bool ok = 1;
    for (int i = 1; i <= n + m && ok; ++i)
      if (!vis[i]) ok &= bfs(i);
    if (ok) printf("Yes\n");
    else printf("No\n");
  }
  return 0;
}

码农公寓

大概是最后一篇题解，其实只是想颓废一下打个故事

Solution

相关文章