USACO2008.通信线路

题目

340. 通信线路

算法标签: 分层图, 二分, 最短路

思路

典型的分层图最短路问题, 可以直接计算, 但是注意到空间限制只有$64MB$, 如果使用分层图进行计算可能导致空间不够, 因此考虑二分做法, 注意到答案是具有二分性质, 对于当前电缆花费$mid$, 如果答案小于$mid$需要升级的电缆数量就要超过$k$, 如果答案大于$mid$, 需要升级电缆的数量可以小于等于$k$的, 因此可以进行二分, 时间复杂度$O(m{\log }^{2}n)$

二分 + $spfa$循环队列 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

const int N = 1010, M = 20010;

int n, m, k;
int head[N], ed[M], ne[M], w[M], idx;
int d[N];
bool vis[N];

void add(int u, int v, int val) {
   
	ed[idx] = v, ne[idx] = head[u], w[idx] = val, head[u] = idx++;
}

// >= mid的线缆需要进行升级, 返回升级电缆数量是否 <= k
bool check(int mid) {
   
	memset(d, 0x3f, sizeof d);
	memset(vis, false, sizeof vis);

	int q[N];
	int h = 0, t = 0;
	d[1] = 0;
	vis[1] = true;
	q[t++] = 1;

	// 循环队列
	while (h != t) {
   
		int u = q[h++];
		if (h == N) h = 0;
		vis[u] = false;

		for (int i = head[u]; ~i; i = ne[i]) {
   
			int v = ed[i];
			int n_val = w[i] > mid;
			if (d[u] + n_val < d[v]) {
   
				d[v] = d[u] + n_val;
				if (!vis[v]) {
   
					q[t++] = v;
					if (t == N) t = 0;
					vis[v] = true;
				}
			}
		}
	}

	return d[n] <= k;
}

int main() {
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	memset(head, -1, sizeof head);
	cin >> n >> m >> k;
	for (int i = 0; i < m; ++i) {
   
		int u, v, w;
		cin >> u >> v >> w;
		add(u, v, w);
		add(v, u, w);
	}

	int l = 0, r = 1e6 + 10;
	while (l < r) {
   
		int mid = l + r >> 1;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}

	int ans = l;
	if (ans == 1e6 + 10) ans = -1;

	cout << ans << "\n";
	return 0;
}

分层图套$dijkstra$

$d[i][j]$代表到达节点$i$并且使用的免费边的个数是$j$的路径上的最大边权, 算法时间复杂度$O(MK\log (N\times K))$

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

const int N = 1010, M = 20010, K = 1010, INF = 0x3f3f3f3f;

int n, m, k;
int head[N], ed[M], ne[M], w[M], idx;
struct State {
   
	int u, used, max_val;
	bool operator< (const State &s) const {
   
		return max_val > s.max_val;
	}
};
int d[N][K];

void add(int u, int v, int val) {
   
	ed[idx] = v, ne[idx] = head[u], w[idx] = val, head[u] = idx++;
}

int main() {
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	memset(head, -1, sizeof head);

	cin >> n >> m >> k;
	for (int i = 0; i < m; ++i) {
   
		int u, v, w;
		cin >> u >> v >> w;
		add(u, v, w), add(v, u, w);
	}

	memset(d, 0x3f, sizeof d);
	d[1][0] = 0;
	priority_queue<State> q;
	q.push({
   1, 0, 0});

	int ans = INF;
	while (!q.empty()) {
   
		auto [u, used, max_val] = q.top();
		q.pop();

		// 存在更小的答案, 跳过
		if (max_val > d[u][used]) continue;
		if (u == n) {
   
			ans = min(ans, max_val);
			continue;
		}

		for (int i = head[u]; ~i; i = ne[i]) {
   
			int v = ed[i];
			int n_val = max(max_val, w[i]);

			// 不使用免费的边
			if (n_val < d[v][used]) {
   
				d[v][used] = n_val;
				q.push({
   v, used, n_val});
			}
			// 当前边免费
			if (used < k) {
   
				if (max_val < d[v][used + 1]) {
   
					d[v][used + 1] = max_val;
					q.push({
   v, used + 1, max_val});
				}
			}
		}
	}

	if (ans == INF) ans = -1;
	cout << ans << "\n";
	return 0;
}