P5304 [GXOI/GZOI2019] 旅行者
原题链接：P5304 [GXOI/GZOI2019] 旅行者
Tag：最短路、二进制分组
题目描述
给定一个有 \(n\) 个点 \(m\) 条边的有向图，第 \(i\) 条边权记为 \(z_i\)， 给定 \(k\) 个关键点，给定关键点集合 \(V'\) 求 \(\min \{ \dis(u,v) \vert u,v\in V',u \neq v\}\)。
数据说明： 多测，\(T \leq 5\)。
\(n \leq 10^5\)，\(m \leq 5 \times 10 ^ 5\)， \(2 \leq k \leq n\)，\(1 \leq x,y \leq n\)，\(1 \leq 边权 \leq 2 \times 10^9\)。
分析
首先分析题目要求的是什么， 求的是一个集合中两两最短路中最短的一个， 一开始想到 \(\text{Floyd}\)， 但是看到数据范围发现 \(\text{Floyd}\) 的 \(\Theta(n^3)\) 显然是过不去的。 之后我们思考一下 \(\text{Dijkstra}\)， 如果我们对于每一个关键点跑一次 \(\text{Dijkstra}\)， 时间复杂度是 \(O(kmlogm)\) 的，显然这样也是过不去的。 我们可以考虑一下怎么样才能少跑几次 \(\text{Dijkstra}\)，
于是可以想到对这些关键点进行分组， 比如我们把这些关键单分为 \(S\)、\(T\) 两组。 我们假设有一个源点用一个边权位 \(0\) 的边连接了所有 \(S\) 中的点， 有一个汇点连接了所有 \(T\) 中的点， 这个时候我们以源点作为起始点跑 \(\text{Dijkstra}\) 就可以了， 之后我们查询 \(T\) 组中的每一个点距离这个源点的距离，拿这个距离去更新答案。 值得注意的是，由于图存的是单向边，所以我们跑完一次 \(\text{Dijkstra}\) 之后， 要交换 \(S\) 集合与 \(T\) 集合的意义再跑一次 \(\text{Dijkstra}\) 就可以了。
下一个问题是如何进行分组， 可以使用二进制分组， 二进制分组的原理是两个不同的数字在二进制表示下一定至少有一位二进制是不一样的， 所以我们按照每一位二进制是 \(0\) 还是 \(1\)，把数字多次分组， 就可以保证每两个元素至少存在一种分组会被分到不同的组里。 不难想到二进制分组的复杂度是 \(\Theta(logk)\) 的。
于是我们得出了一种二进制分组后跑 \(\text{Dijkstra}\) 的做法， 这个做法的时间复杂度是 \(O(m \log m \log k)\) 的。
值得一提的事情是，根据 \(k\) 的取值范围， 我们可以知道最多进行17组拆分，于是我们可以直接写一个执行17次的循环。
注意开long long，我#define int long long了没复制进代码区。
代码实现
void NeverSayNever() {
//cout << log2(100000) << endl;//17
int n,m,k; cin >> n >> m >> k;
vector<vector<PII>> adj(n+1);
for (int i = 0; i < m ; ++i) {
int u,v,w;cin >> u >> v >> w;
adj[u].push_back({v,w});
}
vector<int> dis(n+1,LLONG_MAX);
vector<bool> vis(n+1,false);
auto dijkstra = [&](vector<int> &s){
priority_queue<PII,vector<PII>,greater<PII>> pq;
for(auto &x : s){
dis[x] = 0;
pq.push({0,x});
}
while(!pq.empty()){
auto [w,cur] = pq.top();
pq.pop();
if(vis[cur]) continue;
vis[cur] = 1;
for(auto nxt : adj[cur]){
auto [to,val] = nxt;
if(dis[to] > dis[cur] + val){
dis[to] = dis[cur] + val;
pq.push({dis[to],to});
}
}
}
};
vector<int> key(k);
for(auto &x : key) cin >> x;
int ans = LLONG_MAX;
for(int i = 1;i <= 17;i++){
vector<int> S,T;
for(auto &x : key){
if((x >> i) & 1){
S.push_back(x);
}else{
T.push_back(x);
}
}
if(S.size()==0||T.size() == 0) continue;
std::fill(dis.begin(), dis.end(),LLONG_MAX);
std::fill(vis.begin(), vis.end(),false);
dijkstra(S);
for(auto &x : T){
ans = min(ans,dis[x]);
}
std::fill(dis.begin(), dis.end(),LLONG_MAX);
std::fill(vis.begin(), vis.end(),false);
dijkstra(T);
for(auto &x : S){
ans = min(ans,dis[x]);
}
}
cout << ans << endl;
}
额外思考
考虑一下二进制分组的应用场景， 当我们有一个集合，要考虑这个集合中的两两之间的关系时或许可以使用二进制分组。
再考虑一下二进制分组的本质， 实际上是把一个完全图分成了 \(\text{log}\) 个二分图。
日志
本页面创建于 2024/7/17 15:51
此时我正在上小学期。