T5 可恶の施工：最小生成树、贪心

题意简化

给定一个无向带权连通图，求在保证图连通的前提下，最少删除多少条边使得剩余边的总权值不超过给定的限制 $p$。若无法满足条件，输出 -1。

关键观察

• 最优解的结构一定是 保留权值较小的边，同时保证图的连通性。
• 这与 最小生成树 (MST) 的性质一致：MST 是权值和最小的连通子图。
• 因此，问题转化为：在 MST 的基础上，尽可能多地保留权值小的额外边，使得总权值不超过 $p$。

算法思路

1. 构建最小生成树：

   • 使用 Kruskal 算法求出 MST，记录其权值和 $sum_{\text{MST}}$ 和使用的边数 $n-1$。
   • 若 $sum_{\text{MST}} > p$，直接输出 -1（无解）。

2. 贪心添加额外边：

   • 将 非 MST 边 按权值从小到大排序。
   • 依次尝试添加这些边，直到总权值超过 $p$。
   • 最终删除的边数为 总边数 $m$ - 保留的边数。

时间复杂度分析

• Kruskal 算法：排序边 $O(m \log m)$，并查集操作 $O(m \alpha(n))$，总体 $O(m \log m)$。
• 贪心添加额外边：遍历至多 $m$ 条边，$O(m)$。
• 总复杂度：$O(T \cdot m \log m)$，其中 $T$ 为测试用例数量。

部分分策略

测试点	数据范围	特殊性质	可用算法	预计得分
1-2	$N, M \leq 10$	无	暴力枚举删边组合	10pts
3-4	$N, M \leq 100$	无	枚举保留边数 + Kruskal	30pts
5	$N \leq 10^5, M \leq 2e5$	所有边权相等	贪心保留最多边	25pts
6	$M = N-1$（树结构）	树边权和是否超过 $p$	直接判断 $sum \leq p$	10pts
7-10	$N \leq 10^5, M \leq 2e5$	无	正解算法	100pts

特殊性质说明：

• 性质 A：所有边权相等时，保留尽可能多的边即可，无需考虑权值大小。
• 性质 B：图为树时，若 $sum_{\text{MST}} > p$ 则无解，否则必须保留全部树边（不能删除任何边，否则不连通）。

正解代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;
struct node{
	int from, to, len;
	bool operator < (const node &b) const{
		return len < b.len;
	}
}edge[100005], edge2[100005];
int father[100005];
int find(int n){return (father[n] == n ? n : father[n] = find(father[n]));}
bool merge(int x, int y){
	int n = find(x), m = find(y);
	if(n == m) return 0;
	father[min(n, m)] = max(n, m);
	return 1;
}
int n, m, k, ct, ctt, cttt;
void solve(){
	cin >> n >> m >> k;
	ct = ctt = cttt = 0;
	for(int i = 1; i <= n; i++) father[i] = i;
	for(int i = 1; i <= m; i++){
		cin >> edge[i].from >> edge[i].to >> edge[i].len;
	}
	sort(edge + 1, edge + m + 1);
	for(int i = 1; i <= m; i++){
		if(merge(edge[i].from, edge[i].to)){
			ct++;
			ctt += edge[i].len;
			if(ct == n - 1){
				for(int j = i + 1; j <= m; j++) edge2[++cttt] = edge[j];
				break;
			}
		}else{
			edge2[++cttt] = edge[i];
		}
	}
	if(ctt > k || ct < n - 1){
		cout << "NO\n";
		return;
	}
	for(int i = 1; i <= cttt; i++){
		ctt += edge2[i].len, ct++;
		if(ctt > k){
			cout << m - ct + 1 << '\n';
			return;
		}
	}
	cout << "0\n";
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while(t--) solve();

	return 0;
}