CodeForce 1468J. Road Reform

题目链接

https://codeforces.com/problemset/problem/1468/J

题意

给定一张无向图，你有一个操作是使某一边的边权加一或减一。要求一个图的生成树，树的所有边的边权的最大值恰好为k，求最小的操作数。

思路

首先把所有小于等于 (k) 的边都选上，那么此时如果所有点还不在一个集合， 就将大于 (k) 的边 按与 (k) 的绝对值作为权值跑最小生成树， 然后将权降为 (k) 。
如果小于等于 (k) 的边集合能构成树， 那么选择一条距离 (k) 最近的边变为 (k) 。

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 50;
int a[maxn], b[maxn];
ll c[maxn];
int far[maxn];
int Rank[maxn];
int find(int x){
	if(far[x] == x)return x;
	else return far[x] = find(far[x]);
}
void unite(int x,int y){
	x = find(x);
	y = find(y);
	if(x == y) return;

	if(Rank[x] > Rank[y]) far[y] = x;
	else
	{
		far[x] = y;
		if(Rank[x] == Rank[y]) Rank[y]++;
	}
}
bool check(int x,int y){
	return find(x) == find(y);
}
struct edge{
	int u,v;
	ll cost;
};
edge es[maxn];
bool cmp(const edge& e1,const edge& e2){
	return e1.cost < e2.cost;
}
ll kruskal(int E){
	sort(es, es + E, cmp);
	ll ans = 0;
	for(int i = 0;i < E;i++)
	{
		if(!check(es[i].v,es[i].u))
		{
			unite(es[i].v,es[i].u);
			ans += es[i].cost;
		}
	}
	return ans;
}
int cnt;
void add(int u, int v, ll w){
    es[cnt].u = u, es[cnt].v = v, es[cnt].cost = w;
    cnt++;
}
int init(int n){
    for(int i = 0;i <= n;i++){
        far[i] = i;
    }
    cnt = 0;
}
int main()
{
    std::ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while(t--){
        int n, m;
        ll k;
        cin >> n >> m >> k;
        init(n);
        ll ans = 0;
        ll mi = 1e18;
        for(int i = 0;i < m;i++){
            cin >> a[i] >> b[i] >> c[i];
            if(c[i] <= k){
                unite(a[i], b[i]);
            }
            else add(a[i], b[i], c[i] - k);
            mi = min(abs(k - c[i]), mi);
        }
        ans = kruskal(cnt);
        if(ans) cout << ans << endl;
        else cout << mi << endl;
    }
    return 0;
}
``