P2323 [HNOI2006] 公路修建问题

#include <bits/stdc++.h>
#define re register int 
using namespace std;
const int N = 1e4 + 10, M = 2e4 + 10;
struct edge
{
	int x, y, w1, w2, id;
}e[M];
struct Res
{
	int id, op;
}res[M], tmp[M];

bool cmp1(edge i, edge j) { return i.w1 < j.w1; }
//bool cmp2(edge i, edge j) { return i.w2 < j.w2; }
bool cmp_res(Res i, Res j) { return i.id < j.id; }

int top, cnt_res, fa[N], ans, l, r;
int n, k, m;
 
int find(int x)
{
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void merge(int x, int y)
{
	fa[find(x)] = find(y);
}

bool kruskal(int mid)
{
	for (re i = 1; i <= n; i ++) fa[i] = i;
	memset(tmp, 0, sizeof(tmp));
	int cnt = 0;
	int kk = k;
	while (kk)
	{
		edge a = e[mid];
		if (find(a.x) != find(a.y))
		{
			merge(a.x, a.y);
			tmp[++cnt] = (Res){a.id, 1};
		}
		kk --;
		mid --;
	}
//	sort(e + 1, e + top + 1, cmp2);
	for (re i = 1; i <= top; i ++)
	{
		edge a = e[i];
		if (find(a.x) != find(a.y) && a.w2 <= mid) // a.w2 <= mid <--- tip 1
		{
			merge(a.x, a.y);
			tmp[++cnt] = (Res){a.id, 2};
		}	
	}
	int root = 0;
	for (re i = 1; i <= n ; i ++)
		if (fa[i] == i) root ++;
	if (root == 1)
	{
		for (re i = 1; i <= cnt; i ++)
		{
			res[i].id = tmp[i].id;
			res[i].op = tmp[i].op;
			
		}
		cnt_res = cnt;
		return true;
	}
	return false;
}

void search()
{
	sort(e + 1, e + top + 1, cmp1);
	l = k, r = m;
	while (l <= r)
	{
		int mid = (l + r) >> 1;
//		cout << mid << '\n';
		if (kruskal(mid))  
		{
			ans = e[mid].w1;
			r = mid - 1;
		} 
		else l = mid + 1;
	}
}

void print()
{
	cout << ans << '\n';
	sort(res + 1, res + cnt_res + 1, cmp_res);
	for (re i = 1; i <= cnt_res; i ++)
		cout << res[i].id << ' ' << res[i].op << '\n';
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> k >> m;
	m--;
	for (re i = 1; i <= m; i ++)
	{
		int x, y, w1, w2;
		cin >> x >> y >> w1 >> w2;
		e[++top] = (edge){x, y, w1, w2, top};
	}
	search();
	print();
	
	return 0;
}