[FJOI2018]所羅門的寶藏

大概是最后一篇題解,其實只是想頹廢一下打個故事

據古代傳說記載,所羅門王即是智慧的代表,又是財富的象征。他建立了強大而富有的國家,聚集了大批的黃金象牙和鉆石,并把這些價值連城的珍寶藏在一個神秘的地方,這就是萬世矚目的“所羅門的寶藏”。多少個世紀以來,人們一直在尋找這批早已失落的古代文明寶藏,尋找盛產黃金和鉆石的寶地。曾經追尋所羅門王寶藏的冒險者們都一去不回,至今沒有人解開這個迷題。亨利男爵在一次幸運的旅行中以外地得到了三百年前一本葡萄牙貴族留下的寫在羊皮卷上的所羅門王的寶藏圖和一本尋寶秘笈。在這張藏寶圖的誘惑下,亨利男爵邀請約翰上校和勇敢的獵象人夸特曼開始了尋找埋藏在黑暗地底的所羅門王寶藏的艱險歷程。他們橫穿渺無邊際的沙漠和濃蔭蔽日的原始森林,穿越洶涌澎湃的激流險灘,翻越高聳入云的峻嶺雪山,飽嘗沙漠的酷熱和冰雪嚴寒,在藏寶圖的指引下來到了非洲一個原始的神秘國度庫庫安納。這里有殘酷的人殉制度,有一個擁有一千個妻室的獨眼暴君特瓦拉,有像兀鷲一般丑陋詭詐的老而不死的女巫加古爾,還有美麗聰明的絕代佳人弗拉塔。在這片陌生而又險象環生的土地上三位尋寶英雄歷盡艱辛。終于在絕代佳人弗拉塔的幫助下在海底深處找到了珍藏這批價值連城寶藏的巨大藏寶洞。然而,在女巫加古爾的精心策劃下,一場滅頂之災正在悄悄逼近。

藏寶洞的洞門十分堅固且洞門緊閉,如果不知道開啟洞門的秘密是無法打開藏寶洞的洞門的。在藏寶洞的洞門一側有一個奇怪的矩形密碼陣列。根據尋寶秘笈記載,在密碼陣列的每行的左側和每列的頂端有一顆紅寶石按鈕。每個按鈕都可以向左或向右轉動。每向左轉動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

22 2 41 1 01 2 02 1 22 2 22 2 41 1 01 2 02 1 22 2 1

輸出 #1

YesNo

說明/提示

對于 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;}