P2323 [HNOI2006] 公路修建问题

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 10010010;
int n,k,m;
int num,ans,maxx=-1,tot=1;
int fu[N],vis[N];
int cnt;
struct op{
	int now,to,w,lower,dui;
}opt[N];
int dui[N],lower[N];
bool cmp(op a,op b){
	return a.w < b.w;
}
inline int root(int a){
	return fu[a]==a?a:fu[a]=root(fu[a]);
}
void merge(int a,int b){
	fu[root(a)] = root(b);
}
int kru(int shu){
	int cntt=0,number=0;
	for(int i=1;i<=N;i++) fu[i] = i;
    for(int i=shu;i>=1;i--){
    	if(opt[i].lower==1){
    		if(root(opt[i].now)!=root(opt[i].to)){
    			merge(opt[i].now,opt[i].to);
    			number++;
    			cntt++;
    			
			}
			else number++;
		}
		else {
			if(root(opt[i].now)!=root(opt[i].to)){
    			merge(opt[i].now,opt[i].to);
    			cntt++;
			}
		}
		if(number>=k&&cntt==n-1) return 1;
	}
	return 0;
}
int kru1(int shu){
	int cntt=0;
	for(int i=1;i<=N;i++) fu[i] = i;
    for(int i=shu;i>=1;i--){
    		if(root(opt[i].now)!=root(opt[i].to)){
    			merge(opt[i].now,opt[i].to);
    			dui[tot] = opt[i].dui;
    			lower[tot] = opt[i].lower;
    			tot++;
    			cntt++;
			}
		if(cntt==n-1) return 1;
	}
	tot = 1;
	return 0;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k >> m;
	for(int i=1;i<m;i++)  {
		int a,b,c,d;
		cnt++;
		cin >> a >> b >> c >> d;
		opt[cnt].now = a,
		opt[cnt].to = b;
		opt[cnt].w = c;
		opt[cnt].lower = 1;
		opt[cnt].dui = i;
		cnt++;
		opt[cnt].now = a,
		opt[cnt].to = b;
		opt[cnt].w = d;
		opt[cnt].lower = 2;
		opt[cnt].dui = i;
	}
	sort(opt+1,opt+1+cnt,cmp);
	//cout << "\n";
//	for(int i=1;i<=cnt;i++) cout << opt[i].now << " " << opt[i].to << " " << opt[i].w << " " << opt[i].lower << "\n";
	//cout << "\n";
	int l=1,r=cnt,mid=(l+r)>>1;
	while(l<r){
		int c = kru(mid);
		if(c) {
		r = mid-1;
		maxx = opt[mid].w;
		}
		else l = mid+1;
		mid = (l+r)>>1;
	}
    int yu;
	cout << maxx << "\n";
	for(int i=1;i<=cnt;i++){
		if(opt[i].w == maxx){
			if(kru1(i)) break;
		} 
	}
	for(int i=1;i<tot;i++){
		cout << dui[i] << " " << lower[i] << "\n";
	}
	return 0;
}