【分層圖虛擬節點】 P11327 [NOISG 2022 Finals] Voting Cities|普及+

本文涉及知識點

C++圖論

P11327 [NOISG 2022 Finals] Voting Cities

題目描述

你所在的國家的國家主席 $\bf{Lord\ Pooty}$ 將要退休了！他希望選擇他的一個兒子作為他的繼承人，出于各方面因素的考慮，他決定進行一次投票！他所在的國家中共有 $N$ 個國家，編號從 $0$ 到 $N ? 1$ ，其中 $K$ 個城市是可以投票的，第 $i$ 個可以投票的城市編號為 $T_i$ 。

你認為，投票是你作為公民應該做的義務。于是你決定去某一個能投票的城市參與投票！所有城市之間有 $E$ 條公路，第 $j$ 條公路單向從城市 $U_j$ 通往城市 $V_j$ ，通過這條公路需要交過路稅 $C_j$ 。幸運的是，為了更好的完成投票，國家頒布了一系列過路稅優惠政策。

具體的來說，你有 $5$ 種優惠券可以購買，使用第 $x$ 種優惠券通過一條過路稅為 $y$ 的公路時，只需要付 $\times (10x)\%$ 。但是，由于很多人都想投票，需要使用優惠券，所以每一種優惠券你最多只能買 $1$ 張。

你是個大忙人，你既不知道從哪個城市出發，也不知道每種優惠券的價格。你現在設想了 $Q$ 種情況，包括出發城市 $S$ 和優惠券價格 $P_1,P_2,P_3,P_4$ 和 $P_5$ 。在有些情況下某些優惠券甚至已經被搶光了，你不能購買它們，此時這些無法購買的優惠券的價格將被表示為 $? 1$ 。

現在你需要分別對這 $Q$ 種情況，輸出到達某一個投票城市的最小花費。請注意，你不一定總是能通過公路到達某一個投票城市，如果不能到達，你應該輸出 $? 1$ 。

輸入格式

第一行，三個整數 $N, E, K$ 。

第二行， $K$ 個整數，表示 $T_i$ 。

接下來 $E$ 行，每行三個整數 $U_j,V_j,C_j$ 。保證 $C_j$ 是 $10$ 的倍數。

接下來一行一個整數 $Q$ 。

接下來 $Q$ 行，每行 $6$ 個整數 $S,P_1,P_2,P_3,P_4,P_5$ 。

輸出格式

共 $Q$ 行，每行一個整數表示答案。

輸入輸出樣例 #1

輸入 #1

3 2 1
2
0 1 100
1 2 200
1
0 10 20 1000 2000 -1

輸出 #1

輸入輸出樣例 #2

輸入 #2

2 0 1
1
1
0 -1 -1 -1 -1 -1

輸出 #2

-1

輸入輸出樣例 #3

輸入 #3

6 3 2
4 5
0 4 100
1 4 200
2 5 300
4
0 -1 -1 -1 -1 -1
1 20 40 10 100 4
2 1 2 3 4 0
3 0 -1 0 0 0

輸出 #3

說明/提示

【樣例 #1 解釋】

該樣例滿足 $\tt{Subtask\ 4,5,7,8}$ 的限制。

對于這種情況，最佳方案是在 $\to 2$ 的道路上使用一張 $2$ 類優惠券，在 $\to 1$ 的道路上使用一張 $1$ 類優惠券，花費為 $200 \times (1 - \frac{2}{10})+100 \times (1 - \frac{1}{10})\%+10+20=160+90+10+20=280$ 。

【樣例 #2 解釋】

該樣例滿足所有 $\tt{Subtask}$ 的限制。

沒有道路可以從出發城市到達一個投票城市，所以輸出 $? 1$ 。

【樣例 #3 解釋】

該樣例滿足 $\tt{Subtask\ 7,8}$ 的限制。

【數據范圍】

$\tt{Subtask}$	分值	特殊性質
$1$	$5$	對于所有 $i$ ， $P_i=-1$ 。換句話說，沒有可用的優惠券。 $Q = 1, K = 1$
$2$	$5$	對于所有 $i$ ， $P_i=-1$ 。換句話說，沒有可用的優惠券。 $K = 1$
$3$	$5$	對于所有 $i$ ， $P_i=-1$ 。換句話說，沒有可用的優惠券。
$4$	$5$	$Q = 1, K = 1$
$5$	$5$	$K = 1$
$6$	$10$	對于每種情況，最多有 $1$ 張優惠券可用。
$7$	$15$	$\le N \le 100,1 \le E \le 1000$
$8$	$50$	無

對于 $100\%$ 的數據， $\le N \le 5000,0 \le E \le 10000,1 \le Q \le 100,0 \le K \le N,0 \le T_i < N,1 \le C_i \le 10^9,-1 \le P_i \le 10^9$ ，且對于所有 $\le i < j \le K$ ，有 $T_i \not = T_j$ ；對于所有 $\le i \le E$ ，保證 $C_i$ 是 $10$ 的倍數， $\le U_i,V_i < N,U_i\not=V_i$ 。

分層圖

32層的分層圖。
層內都是沒有優惠的邊。
第0層到第 $2^i$ 層的邊，邊權都是按 $P_{i+1}$ 優惠；
第m層，如果 $m 位與 (1 << i) 不成立$ ，則有邊連向 $m ∣ (1 << i)$ 邊權，邊權都是按 $P_{i+1}$ 優惠。否則無邊。
性質一：任意0層到m層的路徑，都包括且僅包括一條按P_{i+1}優化的邊，(1<<i)&m成立$

時間復雜度

32層邊數大約M= $10^6$
如果每個查詢都用迪氏堆優化跑最短路，則時間復雜度：O(QMlogM) 超時。

超級終點

增加一個虛擬終點 $E = 32 N$ 。所有邊反向,E只向0層的T，邊權為0。以E為起點求最短路。
各查詢的優惠券價格不一樣，如何處理？
建圖時，假定價格是0。
第m層的真實價格：建圖價格+ $\sum_{(1<<i)位與m)} P_{i+1}的購買價格$
時間復雜度降到 $Ml o g M$ 。

代碼

核心代碼

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>
#include<list>
#include<array>#include <bitset>
#include <chrono>
using namespace std::chrono;
using namespace std;template<class T1, class T2>
std::istream& operator >> (std::istream& in, pair<T1, T2>& pr) {in >> pr.first >> pr.second;return in;
}template<class T1, class T2, class T3 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t);return in;
}template<class T1, class T2, class T3, class T4 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);return in;
}template<class T1, class T2, class T3, class T4, class T5 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4, T5>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t) ;return in;
}template<class T1, class T2, class T3, class T4, class T5, class T6 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4, T5, T6>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t) >> get<5>(t) ;return in;
}template<class T1, class T2, class T3, class T4, class T5, class T6, class T7 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4, T5, T6, T7>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t) >> get<5>(t) >> get<6>(t);return in;
}template<class T = int>
vector<T> Read() {int n;cin >> n;vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;
}
template<class T = int>
vector<T> ReadNotNum() {vector<T> ret;T tmp;while (cin >> tmp) {ret.emplace_back(tmp);if ('\n' == cin.get()) { break; }}return ret;
}template<class T = int>
vector<T> Read(int n) {vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;
}template<int N = 1'000'000>
class COutBuff
{
public:COutBuff() {m_p = puffer;}template<class T>void write(T x) {int num[28], sp = 0;if (x < 0)*m_p++ = '-', x = -x;if (!x)*m_p++ = 48;while (x)num[++sp] = x % 10, x /= 10;while (sp)*m_p++ = num[sp--] + 48;AuotToFile();}void writestr(const char* sz) {strcpy(m_p, sz);m_p += strlen(sz);AuotToFile();}inline void write(char ch){*m_p++ = ch;AuotToFile();}inline void ToFile() {fwrite(puffer, 1, m_p - puffer, stdout);m_p = puffer;}~COutBuff() {ToFile();}
private:inline void AuotToFile() {if (m_p - puffer > N - 100) {ToFile();}}char  puffer[N], * m_p;
};template<int N = 1'000'000>
class CInBuff
{
public:inline CInBuff() {}inline CInBuff<N>& operator>>(char& ch) {FileToBuf();while (('\r' == *S) || ('\n' == *S) || (' ' == *S)) { S++; }//忽略空格和回車ch = *S++;return *this;}inline CInBuff<N>& operator>>(int& val) {FileToBuf();int x(0), f(0);while (!isdigit(*S))f |= (*S++ == '-');while (isdigit(*S))x = (x << 1) + (x << 3) + (*S++ ^ 48);val = f ? -x : x; S++;//忽略空格換行		return *this;}inline CInBuff& operator>>(long long& val) {FileToBuf();long long x(0); int f(0);while (!isdigit(*S))f |= (*S++ == '-');while (isdigit(*S))x = (x << 1) + (x << 3) + (*S++ ^ 48);val = f ? -x : x; S++;//忽略空格換行return *this;}template<class T1, class T2>inline CInBuff& operator>>(pair<T1, T2>& val) {*this >> val.first >> val.second;return *this;}template<class T1, class T2, class T3>inline CInBuff& operator>>(tuple<T1, T2, T3>& val) {*this >> get<0>(val) >> get<1>(val) >> get<2>(val);return *this;}template<class T1, class T2, class T3, class T4>inline CInBuff& operator>>(tuple<T1, T2, T3, T4>& val) {*this >> get<0>(val) >> get<1>(val) >> get<2>(val) >> get<3>(val);return *this;}template<class T = int>inline CInBuff& operator>>(vector<T>& val) {int n;*this >> n;val.resize(n);for (int i = 0; i < n; i++) {*this >> val[i];}return *this;}template<class T = int>vector<T> Read(int n) {vector<T> ret(n);for (int i = 0; i < n; i++) {*this >> ret[i];}return ret;}template<class T = int>vector<T> Read() {vector<T> ret;*this >> ret;return ret;}
private:inline void FileToBuf() {const int canRead = m_iWritePos - (S - buffer);if (canRead >= 100) { return; }if (m_bFinish) { return; }for (int i = 0; i < canRead; i++){buffer[i] = S[i];//memcpy出錯			}m_iWritePos = canRead;buffer[m_iWritePos] = 0;S = buffer;int readCnt = fread(buffer + m_iWritePos, 1, N - m_iWritePos, stdin);if (readCnt <= 0) { m_bFinish = true; return; }m_iWritePos += readCnt;buffer[m_iWritePos] = 0;S = buffer;}int m_iWritePos = 0; bool m_bFinish = false;char buffer[N + 10], * S = buffer;
};typedef pair<long long, int> PAIRLLI;
class  CHeapDis
{
public:CHeapDis(int n, long long llEmpty = LLONG_MAX / 10) :m_llEmpty(llEmpty){m_vDis.assign(n, m_llEmpty);}void Cal(int start, const vector<vector<pair<int, int>>>& vNeiB){std::priority_queue<PAIRLLI, vector<PAIRLLI>, greater<PAIRLLI>> minHeap;minHeap.emplace(0, start);while (minHeap.size()){const long long llDist = minHeap.top().first;const int iCur = minHeap.top().second;minHeap.pop();if (m_llEmpty != m_vDis[iCur]){continue;}m_vDis[iCur] = llDist;for (const auto& it : vNeiB[iCur]){minHeap.emplace(llDist + it.second, it.first);}}}vector<long long> m_vDis;const long long m_llEmpty;
};class Solution {
public:vector<long long> Ans(int N, vector<int>& T, vector<tuple<int, int, int>>& edge, vector<tuple<int, int, int, int, int, int>>& que) {//本題節點編號從0開始	const int NN = N * 32 + 1;CHeapDis dis(NN);vector <vector<pair<int, int>>> neiBo(NN);auto AddEdge = [&](int m, int m1, int p) {for (const auto& [u, v, c] : edge) {neiBo[N * m + v].emplace_back(N * m1 + u, c / 10 * (10 - p));}};for (int i = 0; i < 32; i++) {//層內邊AddEdge(i, i, 0);}for (int m = 0; m < 32; m++) {//層間邊for (int i = 0; i < 5; i++) {const int m1 = m | (1 << i);if (m1 == m) { continue; }AddEdge(m, m1, i + 1);}}for (const auto& i : T) {neiBo.back().emplace_back(i, 0);}dis.Cal(NN - 1, neiBo);vector<long long> ans;for (const auto& [s, p0, p1, p2, p3, p4] : que){if (dis.m_llEmpty == dis.m_vDis[s]) {ans.emplace_back(-1);continue;}vector<int> P = { p0,p1,p2,p3,p4 };long long cur = dis.m_llEmpty;for (int m = 0; m < 32; m++) {long long buy = 0;for (int j = 0; j < 5; j++) {if (m & (1 << j)) {buy += (-1 == P[j]) ? dis.m_llEmpty : P[j];}}cur = min(cur, dis.m_vDis[N * m + s] + buy);}ans.emplace_back((cur >= dis.m_llEmpty) ? -1 : cur);}return ans;}
};int main() {
#ifdef _DEBUGfreopen("a.in", "r", stdin);
#endif // DEBUG	ios::sync_with_stdio(0); cin.tie(nullptr);//CInBuff<> in; COutBuff<10'000'000> ob;int N,E,K;cin >> N >> E >> K ;vector<int> T = Read<int>(K);auto edge = Read<tuple<int, int, int>>(E);auto que = Read<tuple<int, int, int, int, int,int>>();#ifdef _DEBUG	printf("N=%d", N);Out(T, ",T=");Out(edge, ",edge=");Out(que, ",que=");
#endif // DEBUG		auto res = Solution().Ans(N,T,edge,que);for(const auto& i : res ){cout << i << "\n";}return 0;
}

單元測試

	int N;vector<int> T;vector<tuple<int, int,int>> edge;vector<tuple<int, int, int, int, int,int>> que;TEST_METHOD(TestMethod11){N = 3, T = { 2 }, edge = { {0,1,100},{1,2,200} }, que = { {0,10,20,1000,2000,-1} };auto res = Solution().Ans(N, T, edge, que);AssertV({ 280 }, res);}TEST_METHOD(TestMethod12){N = 2, T = { 1 }, edge = {}, que = { {0,-1,-1,-1,-1,-1} };auto res = Solution().Ans(N, T, edge, que);AssertV({ -1 }, res);}TEST_METHOD(TestMethod13){N = 6, T = { 4,5 }, edge = { {0,4,100},{1,4,200},{2,5,300} }, que = { {0,-1,-1,-1,-1,-1},{1,20,40,10,100,4},{2,1,2,3,4,0},{3,0,-1,0,0,0} };auto res = Solution().Ans(N, T, edge, que);AssertV({100,104,150,-1 }, res);}

擴展閱讀

我想對大家說的話
工作中遇到的問題，可以按類別查閱鄙人的算法文章，請點擊《算法與數據匯總》。
學習算法：按章節學習《喜缺全書算法冊》，大量的題目和測試用例，打包下載。重視操作
有效學習：明確的目標及時的反饋拉伸區（難度合適）專注
聞缺陷則喜(喜缺)是一個美好的愿望，早發現問題，早修改問題，給老板節約錢。
子墨子言之：事無終始，無務多業。也就是我們常說的專業的人做專業的事。
如果程序是一條龍，那算法就是他的是睛
失敗+反思=成功成功+反思=成功