chail's Blog
博客 分类 标签
chail's Blog

目录

目录

通信线路（[USACO08JAN] Telephone Lines S）（二分，01最短路）

 收录于  类别 算法足迹
     约 1686 字   预计阅读 8 分钟 

通信线路（[USACO08JAN] Telephone Lines S）（二分，01最短路）

今天练习最短路题目时遇到了一道比较有意思的题：通信线路（[USACO08JAN] Telephone Lines S的简化版）。我们来看看吧：

在郊区有 $N$ 座通信基站，$P$ 条 双向 电缆，第 $i$ 条电缆连接基站 $Ai$ 和 $Bi$。

特别地，$1$ 号基站是通信公司的总站，$N$ 号基站位于一座农场中。

现在，农场主希望对通信线路进行升级，其中升级第 $i$ 条电缆需要花费 $Li$。

电话公司正在举行优惠活动。

农产主可以指定一条从 $1$ 号基站到 $N$ 号基站的路径，并指定路径上不超过 $K$ 条电缆，由电话公司免费提供升级服务。

农场主只需要支付在该路径上剩余的电缆中，升级价格最贵的那条电缆的花费即可。 求至少用多少钱可以完成升级。

第 $1$ 行：三个整数 $N，P，K$。

第$2..P+1$ 行：第 $i+1$ 行包含三个整数$Ai,Bi,Li$。

包含一个整数表示最少花费。

若 $1$ 号基站与 $N$ 号基站之间不存在路径，则输出 $−1$。

$0≤K<N≤1000, 1≤P≤10000, 1≤Li≤1000000$

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6
4

给了一张边权无向图，要寻找从$1$到$N$的最短路，最短路上可以不计$K$条边的权重，只计剩下边的最大权重，找出这个最大权重的最小值。

刚读完这道题后，我怀疑了一下，这道题真的是最短路问题吗？因为这种可以不计某些边的权重的最短路问题我只在分层图见过。对于这道题同样可以考虑一下分层图的做法。

思考：既然可以免去$K$条边，那就建$K+1$层图，再去跑最短路算法，最后每层$N$点的最小值就是答案了。不过我很快就打消了这个念头，因为这里的$K$最大能有$1000$，这么多层图，时间空间复杂度都很大，大概率超时。

但是，后来我看题解时发现确实能用分层图做，建完图之后跑一遍SFPA就可以了。这种做法时间复杂度$O(npk)$，数据严一点就会超时，所以并不是最优解。

最终答案可以抽象为某条路上第$K+1$大的权重，我们能不能从这里入手呢？考虑对Dijkstra进行变形，每次计算的路程是截止当前节点第$K+1$大的权重，这样最后应该能找到答案。不过有个问题：每次该怎么计算第$K+1$大的权重是多少。我们似乎只能用一个数据结构把路给记下来，甚至每次还要查找第$K+1$大的权重。这样的话，好复杂，而且貌似还容易超时。

怎么办呢，没有办法了吗Orz。

这道题有一个特点就是可以免费K条边，为了找最小值我们当然希望让最大的几条边免费。那么摒弃传统的最短路思想，我们只需要找一个阈值权重，这个阈值使得路上大于它的边的数量不大于K，并且这个阈值要尽可能的小。转化到这里，其实已经是一个很经典的二分问题了，二分待定阈值，每次检测该值是否符合要求，符合则继续缩小…是的，这简直可以套一个二分的模板！

接下来就是怎么检查了，以待检查值为阈值，大于它的为$1$，否则为$0$，转换成一个01最短路问题，我们就可以找出以$x$为阈值，大于$x$的边最少的一条路了。那个$x$就是我们要的答案！

这里就是很普通的二分写法了，用位运算除$2$。

while(l<=r){
		int mid = (r+l)>>1;
		if(check(mid)){
			r = mid-1;
			res = mid;
		}
		else l = mid+1;
	}

这里定义了整数对PII，即pair<int,int>。这样就不用再为优先队列重载运算符了，不过要注意的是，first是总权重，second是节点编号值，千万不要搞反了，这会影响优先队列的正常运作。

priority_queue<PII, vector<PII>, greater<PII>> hp;
bool check(int x){
//	cout << "checking " << x << "\n";
	int dis[1005];
	fill(dis, dis+1+n, 1e9);
	bool u[1005] = {false};
	hp.push({0,1});
	while(!hp.empty()){
		PII cp = hp.top();
		hp.pop();
		if(u[cp.second]) continue;
		u[cp.second] = true;
		dis[cp.second] = cp.first;
		if(!rs[cp.second].empty()){
			for(r cr : rs[cp.second]){
				if(u[cr.t]) continue;
				if(cr.l>x) hp.push({cp.first+1, cr.t});
				else hp.push({cp.first, cr.t});
			}
		}
	}
	if(dis[n]<=k) return true;
	else return false;
}

最后给出完整代码：

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
#include <vector>
#include <utility>
#define int long long
using namespace std;
typedef pair<int,int> PII;
struct r{
	int t;
	int l;
};
vector<r> rs[1005];
int n, p, k;
priority_queue<PII, vector<PII>, greater<PII>> hp;
bool check(int x){
//	cout << "checking " << x << "\n";
	int dis[1005];
	fill(dis, dis+1+n, 1e9);
	bool u[1005] = {false};
	hp.push({0,1});
	while(!hp.empty()){
		PII cp = hp.top();
		hp.pop();
		if(u[cp.second]) continue;
		u[cp.second] = true;
		dis[cp.second] = cp.first;
		if(!rs[cp.second].empty()){
			for(r cr : rs[cp.second]){
				if(u[cr.t]) continue;
				if(cr.l>x) hp.push({cp.first+1, cr.t});
				else hp.push({cp.first, cr.t});
			}
		}
	}
	if(dis[n]<=k) return true;
	else return false;
}
signed main(){
	cin >> n >> p >> k;
	for(int i=1;i<=p;++i){
		int a, b, l;
		cin >> a >> b >> l;
		rs[a].push_back({b,l});
		rs[b].push_back({a,l});
	}
	int l=0;
	int r = 1e6+1;
	int res = 1e6;
	while(l<=r){
		int mid = (r+l)>>1;
		if(check(mid)){
			r = mid-1;
			res = mid;
		}
		else l = mid+1;
	}
	if(res==1e6) cout << -1;
	else cout << res;
	return 0;
}
更新于 2026-02-05
 | 主页