专栏文章

题解：P14362 [CSP-S 2025] 道路修复 / road（民间数据）

llovely_nst
P14362题解参与者 1已保存评论 0

文章操作

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

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

[CSP-S 2025] 道路修复 / road

过民间数据了来水一发。
发现 kk 非常小，因此考虑枚举哪些村庄被操作。
使图联通且花费最小，这符合最小生成树的定义。因此考虑建边后跑 Kruskal，时间复杂度 O(2k(m+nk)log⁡(m+nk))O(2^k(m+nk)\log (m+nk))。
这并不能接受，于是考虑缩小边集大小。先说结论：加入一个或多个与所有点都有连边的新点，原图的任意最小生成树与新边集组成图的最小生成树，同时也是新图的最小生成树。
证明：若原图最小生成树上的一条边不再是树边，则一定是有若干条边权更小的边使其两侧联通。当枚举到比该条边边权更大的边时，原图满足的联通关系此时也一定满足，原本无法加的边此时也一定还是加不了，因此是新图最小生成树。
由此，先求出原图的最小生成树边集，之后再做同样的操作即可。时间复杂度 O(mlog⁡m+2k(n+nk)log⁡(n+nk))O(m\log m+2^k(n+nk)\log (n+nk))。
任然不够优。可以使用技术排序优化掉 log⁡\log，或者在外面排序，里面直接扫或者归并优化掉 log⁡\log。

AC Code

CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e4 + 20 , M = 1e6 + 5;
int n , m , k;
struct edge
{
	int u , v , w;
	bool operator < (edge E) const
	{return w < E.w;}
} a[M] , b[M];
int C[11];
int f[N];
int find (int u)
{
	if (f[u] == u) return u;
	return f[u] = find (f[u]);
}
vector <edge> g;
signed main ()
{
	ios::sync_with_stdio (0);
	cin.tie (0) , cout.tie (0);
	cin >> n >> m >> k;
	for (int i = 1;i <= m;i ++)
	{
		cin >> a[i].u >> a[i].v >> a[i].w;
	}
	int cc = 0;
	for (int i = 0;i < k;i ++)
	{
		cin >> C[i];
		for (int j = 1;j <= n;j ++)
		{
			int x;
			cin >> x;
			b[++ cc] = {i , j , x};
		} 
	}
	sort (a + 1 , a + m + 1);
	sort (b + 1 , b + cc + 1);
	for (int i = 1;i <= n;i ++) f[i] = i;
	int ans = 0;
	for (int i = 1;i <= m;i ++)
	{
		int u = find (a[i].u) , v = find (a[i].v);
		if (u != v) f[u] = v , g.push_back (a[i]) , ans += a[i].w;
	}
	int A = 1 << k;
	for (int S = 1;S < A;S ++)
	{
		int p = 1 , sum = 0;
		for (int i = 1;i <= n + k;i ++) f[i] = i;
		for (int i = 0;i < k;i ++) if (S >> i & 1) sum += C[i];
		for (auto [u , v , w] : g)
		{
			while (p <= cc && b[p].w <= w)
			{
				if (S >> b[p].u & 1)
				{
					int fu = find (b[p].u + n + 1) , fv = find (b[p].v);
					if (fu != fv) f[fu] = fv , sum += b[p].w;
				}
				p ++;
			}
			int fu = find (u) , fv = find (v);
			if (fu != fv) f[fu] = fv , sum += w;
			if (sum >= ans) break;
		}
		ans = min (ans , sum);
	}
	cout << ans;
	return 0;
}

评论

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

正在加载评论...