[CF1468J] Road Reform - 最小生成树
Description
给定无向带权图和参数 k,第 i 条边权值为 si,求一棵生成树,并可以对树上边进行修改,每次修改使得边权 +1 或者 -1,使得边权最大值 =k,求最小操作数。
Solution
如果所有边权都小于等于 k,好办,选一条最大的,剩下的随便选
如果存在边权大于等于 k 的,小于 k 的部分中优先选大的(所有小于最大者都可以随便选),大于 k 的部分优先选小的,所以这里的关键是要确定小于 k 的部分中最大的是哪个,好在小于 k 的部分不用计入代价,所以可以先用小于 k 的部分判定连通性,如果已经连通,那么任意选择一条与 k 最接近的即可(不论它是比 k 大还是比 k 小,都不影响结果);如果没有连通,那么从小到大加入若干条大于 k 的,使得图连通即可
简而言之,先将 <=k 的全部加入,如果连通了,那么从所有边中选择一个与 k 最接近的权值作为答案;如果没有连通,从 >k 的中 Kruskal 一下,和作为答案
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
int n, m, k;
cin >> n >> m >> k;
vector<tuple<int, int, int>> edges(m + 2), edges_large, edges_small;
vector<int> values;
for (int i = 1; i <= m; i++)
{
int a, b, c;
cin >> a >> b >> c;
edges[i] = {a, b, c};
if (c > k)
edges_large.push_back(edges[i]);
else
edges_small.push_back(edges[i]);
values.push_back(c);
}
sort(values.begin(), values.end());
vector<int> fa(n + 2);
for (int i = 1; i <= n; i++)
fa[i] = i;
function<int(int)> find = [&](int x) -> int {
return x == fa[x] ? x : fa[x] = find(fa[x]);
};
int tot = 1;
function<void(int, int)> merge = [&](int x, int y) -> void {
x = find(x);
y = find(y);
if (x != y)
fa[x] = y, tot++;
};
for (auto [u, v, w] : edges_small)
merge(u, v);
int flag = tot == n;
if (flag)
{
int i = lower_bound(values.begin(), values.end(), k) - values.begin();
int j = i - 1;
int ans = 1e18;
if (i >= 0 && i < m)
ans = min(ans, abs(k - values[i]));
if (j >= 0 && j < m)
ans = min(ans, abs(k - values[j]));
cout << ans << endl;
}
else
{
int ans = 0;
vector<pair<int, pair<int, int>>> ve;
for (auto [x, y, z] : edges_large)
ve.push_back({z, {x, y}});
sort(ve.begin(), ve.end());
for (int i = 0; i < ve.size(); i++)
{
auto [w, pr] = ve[i];
auto [u, v] = pr;
if (find(u) != find(v))
merge(u, v), ans += w - k;
if (tot == n)
break;
}
cout << ans << endl;
}
}
signed main()
{
ios::sync_with_stdio(false);
int t;
cin >> t;
while (t--)
{
solve();
}
}