专栏文章

题解：AT_abc416_e [ABC416E] Development

CChen78999
AT_abc416_e题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miopbi1c
此快照首次捕获于
2025/12/02 22:56
3 个月前
此快照最后确认于
2025/12/02 22:56
3 个月前
查看原文

题意简述

给定一张无向图，有 NN 个点和 MM 条边，每条边都有一个正的代价。此外，还有 KK 个点有机场，可以用 TT 的代价从任何一个有机场的点到另一个有机场的点。现在有三种操作：
  1. 加边。
  2. 在指定点上建设机场。
  3. 求所有可达点对的最少代价之和。
我们需要处理所有 QQ 个操作，并输出所有第三种操作的结果。

朴素做法

如果我们每遇到一次 3 操作就用 Floyd 求一次全源最短路，那么最坏复杂度为 O(N3Q)O(N^3Q)，代入题目中变量 N≤500N \le 500，Q≤1000Q \le 1000 后，计算得 N3Q=1.25×1011N^3Q = 1.25 \times {10}^{11}，显然无法通过。
所以我们必须考虑优化。

优化

我们可以先考虑操作较少的情况。

没有加边操作和机场的情况

这时，我们可以预先用 Floyd 求一遍最短路并求和，然后可以 O(1)O(1) 回答每个询问，时间复杂度为 O(N3+Q)O(N^3+Q)。

有加边操作的情况

同样地，我们可以预先用 Floyd 求一遍所有点对间的最短路。
当 xx 和 yy 之间添加了一条代价为 tt 的边时，ii 和 jj 之间的最少代价就会变成以下其中之一：
  • 从 ii 出发到达 xx，然后通过新边到达 yy，最后到达 jj 的代价；
  • 从 ii 出发到达 yy，再经过新边到达 xx，然后到达 jj 的代价；
  • 保持不变。
所以此时我们可以先用 O(N3)O(N^3) 预处理，然后 O(N2)O(N^2) 处理每个询问，时间复杂度为 O(N3+N2Q)O(N^3+N^2Q)。

有加边操作和机场的情况

如果每个城市都有机场，那么最多可以得到 N2N^2 条边。如果每建一个机场，就在所有有机场的城镇之间添加边，并重新计算最少代价，总共需要 O(N2)O(N^2) 时间，总时间复杂度将达到 O(N4+N2Q)O(N^4+N^2Q)，无法通过。即使等到操作 3 再执行 Floyd 算法，情况也是一样。

正解

我们注意到，可以维护每个节点到最近机场的最少代价，第 ii 号节点到最近机场的最少代价记作 AiA_i。如果从第 ii 号节点无法到达任何一个机场，则 Ai=∞A_i = \infty。
这样对每个加机场的操作，我们只需要 O(N)O(N) 更新每个点到最近有机场城市的最少代价即可。
注意
对于每个加边操作，加边完成后也要更新每个点到最近有机场城市的最少代价。对应代码95-102行。
例子
考虑以下情况：
一共有 44 个顶点，从第一个点到第二个点代价为 11，从第二个顶点到第三个顶点代价为 100100。
T=10T = 10，节点 3,43,4 有机场。
有以下两个操作：
  1. 添加一条连接点 11 和 33 的边，代价为 22。
  2. 求所有可达点对的最少代价之和。
如果在加边完成后不更新每个点到最近有机场城市的最少代价，则 A1A_1 仍为 101101 （应该为 22），在计算节点 11 到节点 44 的代价时会发生错误。
这时，从第 xx 个节点到第 yy 个节点的代价可表示为以下两者的最小值：
  • 只经过公路的代价。
  • 先到最近的机场，坐飞机到另一个机场后再到第 yy 个节点的总代价，即 Ax+T+AyA_x + T + A_y。
这样，我们可以先 O(N3)O(N^3) 预处理所有点对间最短路径，O(N2)O(N^2) 处理第一种和第三种操作，O(N)O(N) 处理第二种操作，总时间复杂度为 O(N3+KN+N2Q)O(N^3+KN+N^2Q)。

Code

C
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using pii = pair<int, int>;

template<typename I>
inline bool in_range(I num, I minv, I maxv) {
	return num >= minv && num <= maxv;
}

template<typename I>
inline bool out_of_range(I num, I minv, I maxv) {
	return !in_range(num, minv, maxv);
}
#define rep(index,start,end) for(decltype((start)+0) index=(start),__=(end);(index)<=__;++index)
#define all(x) x.begin(),x.end()

template<typename T>
T & chmax(T & a, const T & b) {
	if (b > a) a = b;
	return a;
}
template<typename T>
T & chmin(T & a, const T & b) {
	if (b < a) a = b;
	return a;
}


int n,m,k,T;
vector<pii> edges[510];
ll d[510][510], e[510][510], a[510];
bool airport[510], exists[510][510];
ll dist[510][510];
set<int> hasairport;

void setup() {
	
}

void Floyd() { // Floyd 算法
	rep(k,1,n) rep(i,1,n) rep(j,1,n) {
		chmin(d[i][j], d[i][k] + d[k][j]);
	}
}

void solve(int testcase = 0) {
	cin>>n>>m;
	rep(i,1,n) rep(j,1,n) d[i][j] = 0x3f3f3f3f3f3f3f3fll;
	rep(i,1,n) d[i][i] = 0;
	rep(i,1,m) {
		int u,v;
		ll w;
		cin>>u>>v>>w;
		chmin(d[u][v],w);
		chmin(d[v][u],w);
	}
	Floyd();
	cin>>k>>T;
	int airver = 1;

	memset(a, 0x3f, sizeof(a));
	rep(j,1,k) {
		int x;
		cin>>x;
		airport[x] = true;
		hasairport.insert(x);
		rep(i,1,n) chmin(a[i], d[i][x]);
	}
	int q,ver = 1, nowver = 0, nowairver = 0;
	ll ans = 0;
	cin>>q;
	while (q--) {
		int mode;
		cin>>mode;
		if (mode == 1) {
			int u,v;
			ll w;
			cin>>u>>v>>w;
			chmin(d[u][v],w);
			chmin(d[v][u],w);
			ver++;
			rep(i,1,n) rep(j,1,n) {
				if (d[i][u] < 0x3f3f3f3f3f3f3f3fll){
					chmin(d[i][j], d[i][u] + w + d[v][j]);
					chmin(d[i][j], d[i][v] + w + d[u][j]);
				}

			}

			
			rep(i,1,n) { // 这是一个坑！
				a[i] = 0x3f3f3f3f3f3f3f3fll;
				if (airport[i]) a[i] = 0;
				for (auto j: hasairport) {
					if (i == j) continue;
					chmin(a[i], d[i][j]);
				}
			}

		} else if (mode == 2) {
			int x; cin >> x;
			airport[x] = true;
			hasairport.insert(x);
			ver++;
			airver ++;
			a[x] = 0;
			rep(i,1,n) {
				chmin(a[i], d[i][x]);
			}
		} else {
			// mode = 3
			ll ans = 0;
			rep(i,1,n) rep(j,1,n) {
				ll tmp = min(d[i][j], a[i]+T+a[j]);
				if (tmp < 0x3f3f3f3f3f3f3f3fll) {
					ans += tmp;
				}
				// cout<<tmp<<" \n"[j==n];
			}
			

			cout<<ans<<endl;
			
		}
	}
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	setup();
	int T = 1;
	// cin >> T;
	rep(testcase, 1, T) {
		solve(testcase);
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...