本文涉及知识点
C++图论
P11327 [NOISG 2022 Finals] Voting Cities
题目描述
你所在的国家的国家主席 L o r d P o o t y \bf{Lord\ Pooty} Lord Pooty 将要退休了!他希望选择他的一个儿子作为他的继承人,出于各方面因素的考虑,他决定进行一次投票!他所在的国家中共有 N N N 个国家,编号从 0 0 0 到 N − 1 N-1 N−1,其中 K K K 个城市是可以投票的,第 i i i 个可以投票的城市编号为 T i T_i Ti。
你认为,投票是你作为公民应该做的义务。于是你决定去某一个能投票的城市参与投票!所有城市之间有 E E E 条公路,第 j j j 条公路单向从城市 U j U_j Uj 通往城市 V j V_j Vj,通过这条公路需要交过路税 C j C_j Cj。幸运的是,为了更好的完成投票,国家颁布了一系列过路税优惠政策。
具体的来说,你有 5 5 5 种优惠券可以购买,使用第 x x x 种优惠券通过一条过路税为 y y y 的公路时,只需要付 y × ( 10 x ) % y \times (10x)\% y×(10x)%。但是,由于很多人都想投票,需要使用优惠券,所以每一种优惠券你最多只能买 1 1 1 张。
你是个大忙人,你既不知道从哪个城市出发,也不知道每种优惠券的价格。你现在设想了 Q Q Q 种情况,包括出发城市 S S S 和优惠券价格 P 1 , P 2 , P 3 , P 4 P_1,P_2,P_3,P_4 P1,P2,P3,P4 和 P 5 P_5 P5。在有些情况下某些优惠券甚至已经被抢光了,你不能购买它们,此时这些无法购买的优惠券的价格将被表示为 − 1 -1 −1。
现在你需要分别对这 Q Q Q 种情况,输出到达某一个投票城市的最小花费。请注意,你不一定总是能通过公路到达某一个投票城市,如果不能到达,你应该输出 − 1 -1 −1。
输入格式
第一行,三个整数 N , E , K N,E,K N,E,K。
第二行, K K K 个整数,表示 T i T_i Ti。
接下来 E E E 行,每行三个整数 U j , V j , C j U_j,V_j,C_j Uj,Vj,Cj。保证 C j C_j Cj 是 10 10 10 的倍数。
接下来一行一个整数 Q Q Q。
接下来 Q Q Q 行,每行 6 6 6 个整数 S , P 1 , P 2 , P 3 , P 4 , P 5 S,P_1,P_2,P_3,P_4,P_5 S,P1,P2,P3,P4,P5。
输出格式
共 Q Q Q 行,每行一个整数表示答案。
输入输出样例 #1
输入 #1
3 2 1
2
0 1 100
1 2 200
1
0 10 20 1000 2000 -1
输出 #1
280
输入输出样例 #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
100
104
150
-1
说明/提示
【样例 #1 解释】
该样例满足 S u b t a s k 4 , 5 , 7 , 8 \tt{Subtask\ 4,5,7,8} Subtask 4,5,7,8 的限制。
对于这种情况,最佳方案是在 1 → 2 1 \to 2 1→2 的道路上使用一张 2 2 2 类优惠券,在 0 → 1 0 \to 1 0→1 的道路上使用一张 1 1 1 类优惠券,花费为 200 × ( 1 − 2 10 ) + 100 × ( 1 − 1 10 ) % + 10 + 20 = 160 + 90 + 10 + 20 = 280 200 \times (1 - \frac{2}{10})+100 \times (1 - \frac{1}{10})\%+10+20=160+90+10+20=280 200×(1−102)+100×(1−101)%+10+20=160+90+10+20=280。
【样例 #2 解释】
该样例满足所有 S u b t a s k \tt{Subtask} Subtask 的限制。
没有道路可以从出发城市到达一个投票城市,所以输出 − 1 -1 −1。
【样例 #3 解释】
该样例满足 S u b t a s k 7 , 8 \tt{Subtask\ 7,8} Subtask 7,8 的限制。
【数据范围】
S u b t a s k \tt{Subtask} Subtask | 分值 | 特殊性质 |
---|---|---|
1 1 1 | 5 5 5 | 对于所有 i i i, P i = − 1 P_i=-1 Pi=−1。换句话说,没有可用的优惠券。 Q = 1 , K = 1 Q=1,K=1 Q=1,K=1 |
2 2 2 | 5 5 5 | 对于所有 i i i, P i = − 1 P_i=-1 Pi=−1。换句话说,没有可用的优惠券。 K = 1 K=1 K=1 |
3 3 3 | 5 5 5 | 对于所有 i i i, P i = − 1 P_i=-1 Pi=−1。换句话说,没有可用的优惠券。 |
4 4 4 | 5 5 5 | Q = 1 , K = 1 Q=1,K=1 Q=1,K=1 |
5 5 5 | 5 5 5 | K = 1 K=1 K=1 |
6 6 6 | 10 10 10 | 对于每种情况,最多有 1 1 1 张优惠券可用。 |
7 7 7 | 15 15 15 | 1 ≤ N ≤ 100 , 1 ≤ E ≤ 1000 1 \le N \le 100,1 \le E \le 1000 1≤N≤100,1≤E≤1000 |
8 8 8 | 50 50 50 | 无 |
对于 100 % 100\% 100% 的数据, 1 ≤ N ≤ 5000 , 0 ≤ E ≤ 10000 , 1 ≤ Q ≤ 100 , 0 ≤ K ≤ N , 0 ≤ T i < N , 1 ≤ C i ≤ 1 0 9 , − 1 ≤ P i ≤ 1 0 9 1 \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 1≤N≤5000,0≤E≤10000,1≤Q≤100,0≤K≤N,0≤Ti<N,1≤Ci≤109,−1≤Pi≤109,且对于所有 1 ≤ i < j ≤ K 1 \le i < j \le K 1≤i<j≤K,有 T i ≠ T j T_i \not = T_j Ti=Tj;对于所有 1 ≤ i ≤ E 1 \le i \le E 1≤i≤E,保证 C i C_i Ci 是 10 10 10 的倍数, 0 ≤ U i , V i < N , U i ≠ V i 0 \le U_i,V_i < N,U_i\not=V_i 0≤Ui,Vi<N,Ui=Vi。
分层图
32层的分层图。
层内都是没有优惠的边。
第0层到第 2 i 2^i 2i层的边,边权都是按 P i + 1 P_{i+1} Pi+1优惠;
第m层,如果 m 位与 ( 1 < < i ) 不成立 m 位与(1<<i)不成立 m位与(1<<i)不成立,则有边连向 m ∣ ( 1 < < i ) m|(1<<i) m∣(1<<i)边权,边权都是按 P i + 1 P_{i+1} Pi+1优惠。否则无边。
性质一:任意0层到m层的路径,都包括且仅包括一条按P_{i+1}优化的边,(1<<i)&m成立$
时间复杂度
32层边数大约M= 1 0 6 10^6 106
如果每个查询都用迪氏堆优化跑最短路,则时间复杂度:O(QMlogM) 超时。
超级终点
增加一个虚拟终点 E = 32 N E=32N E=32N。所有边反向,E只向0层的T,边权为0。以E为起点求最短路。
各查询的优惠券价格不一样,如何处理?
建图时,假定价格是0。
第m层的真实价格:建图价格+ ∑ ( 1 < < i ) 位与 m ) P i + 1 的购买价格 \sum_{(1<<i)位与m)} P_{i+1}的购买价格 ∑(1<<i)位与m)Pi+1的购买价格
时间复杂度降到 M l o g M MlogM MlogM。
代码
核心代码
#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);}
扩展阅读
我想对大家说的话 |
---|
工作中遇到的问题,可以按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。 |
学习算法:按章节学习《喜缺全书算法册》,大量的题目和测试用例,打包下载。重视操作 |
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注 |
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。 |
如果程序是一条龙,那算法就是他的是睛 |
失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。