Road Reform
题意
给你一个 n个顶点 m条边的无向图 (没有重边) 要求删掉 m − ( n − 1 ) 条边使得图仍联通 并且权值最大的边与 k 的差值最小
思路
先把所有小于等于k 的边加入新图 然后判断是否连通
如果已经联通 那么有两种选择
1.将已经加入的最大边权增大到 k
2.将大于 k的第一条边加入 并且减少到k
如果没有联通 那么按照边权递增的顺序加入边 直到联通为止
代码
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 1000000007 #define endl '\n' using namespace std; typedef long long LL; typedef pair<int, int>PII; inline LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } const int N = 200010; int n, m, k; int f[N]; struct Node { int u, v, w; }node[N]; void init() { for (int i = 0; i < N; ++i)f[i] = i; } int Find(int x) { return x == f[x] ? x : f[x] = Find(f[x]); } void merge(int a, int b) { f[Find(a)] = Find(b); } bool cmp(Node a, Node b) { return a.w < b.w; } void solve() { cin >> n >> m >> k; init(); for (int i = 1; i <= m; ++i) { int a, b, c; scanf("%d%d%d", &node[i].u, &node[i].v, &node[i].w); } sort(node + 1, node + m + 1, cmp); int cnt = 0; int i; for (i = 1; i <= m; ++i) { if (node[i].w > k)break; int fa = Find(node[i].u); int fb = Find(node[i].v); if (fa != fb) { merge(fa, fb); cnt++; } } //cout << node[i - 1].w << " " << node[i].w << endl; if (cnt == n - 1) { int res = k - node[i - 1].w; if (i <= m)res = min(res, node[i].w - k); printf("%d\n", res); } else { LL res = 0; for (int j = i; j <= m; ++j) { int fa = Find(node[j].u); int fb = Find(node[j].v); if (fa != fb) { cnt++; merge(fa, fb); res += node[j].w - k; } if (cnt == n - 1)break; } cout << res << endl; } } int main() { int t; cin >> t; while(t--) solve(); return 0; }
