Author: lllyouo
Date: 20250224
tag: 最小生成树
link: https://www.luogu.com.cn/problem/P2323

问题描述

link

分析

参考代码

#include <bits/stdc++.h>
using namespace std;

struct Edge {
	int u, v, a, b, id;
} e[20010];

bool cmpa(Edge x, Edge y) {
	return x.a < y.a;
}

bool cmpb(Edge x, Edge y) {
	return x.b < y.b;
}

int n, m, k, ans, flag[20010];
int p[10010];

int find(int x) {
	if (x == p[x]) return x;
	return p[x] = find(p[x]);
}

int main() {
	cin >> n >> k >> m;
	m--;
	
	for (int i = 1; i <= m; i++) {
		cin >> e[i].u >> e[i].v >> e[i].a >> e[i].b;
		e[i].id = i;
	}
	
	for (int i = 1; i <= n; i++) p[i] = i;
	
	sort(e + 1, e + m + 1, cmpa);
	int cnt = 0; 
	for (int i = 1; i <= m; i++) {
		int fu = find(e[i].u);
		int fv = find(e[i].v);
		if (fu != fv) {
			p[fu] = fv;
			ans = max(ans, e[i].a);
			flag[e[i].id] = 1;
			cnt++;
		}
		if (cnt == k) {
			k = i;
			break;
		}
	}
	
	sort(e + k + 1, e + m + 1, cmpb);
	for (int i = k + 1; i <= m; i++) {
		int fu = find(e[i].u);
		int fv = find(e[i].v);
		if (fu != fv) {
			p[fu] = fv;
			ans = max(ans, e[i].b);
			flag[e[i].id] = 2;
		}
	}
	
	cout << ans << endl;
	for (int i = 1; i <= m; i++) {
		if (flag[i]) {
			cout << i << " " << flag[i] << endl;
		}
	}
	
	return 0;
}