Problem
给出n个点、m条边的无向连通图，每条边具有2个边权，一高一低，我们需要选择若干条边，使得图连通的情况下选择至少k条较高边权，输出选择的边中，边权最大值的最小值，输出答案的一半（保证偶数）
Slove
假设每条边只具有1条边权，答案显而易见，跑一遍最小生成树即可，因为最小生成树就是最小瓶颈树
但是如果存在较高边权且需要选至少k个，该怎么办呢？
注意到，Kruskal算法的本质就是贪心，每次选择最小的边，如果二点未连通，则用并查集合并，否则跳过，直到选择n-1条边
所以此时我们可以将所有边权都遍历一遍，当选择较高边权时k-1,如果k=还需要选择的边时，跳过所有较低边权......吗?
不难发现，此时最小生成树=最小瓶颈树不再适用，但我们可以按照这种贪心思路，优先选择k条较高边权，然后再根据需要选择剩下的边权(也包括较高边权，因为有时某一条边的较低边权可能比另一条边的较高边权还要高!)。因为k条高级边始终是要选择的，且高于低级边权。
时间复杂度就是Kruskal的时间复杂度，为\(O(nlogn)\)
Code
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstring>
#include<cstdlib>
#include<list>
#include<map>
#include<queue>
#include<stack>
#include<vector>
using namespace std;
int n,k,m,ans;
int f[10005];
struct p{int st,to,w,idx;bool type;
};
vector<p> g,road;
bool cmp(p a,p b){if(a.w!=b.w)return a.w<b.w;return a.type>b.type;
}
bool cmp1(p a,p b){return a.idx<b.idx;
}
int find(int u){if(f[u]==u)return u;return f[u]=find(f[u]);
}
bool same(int u,int v){return find(u)==find(v);
}
bool unit(int u,int v){if(same(u,v))return false;f[find(u)]=v;return true;
}
void kruskal(){int edge=n-1;for(int i=0;i<g.size();i++){if(k>0&&!g[i].type){continue;}if(k==0){i=0;k--;}if(unit(g[i].st,g[i].to)){k-=g[i].type;edge--;ans=max(ans,g[i].w);road.push_back(g[i]);}if(!edge)break;}
}
int main(){cin>>n>>k>>m;for(int i=1;i<=n;i++)f[i]=i;for(int i=1,st,to,w1,w2;i<m;i++){cin>>st>>to>>w1>>w2;g.push_back({st,to,w1,i,1});g.push_back({st,to,w2,i,0});}sort(g.begin(),g.end(),cmp);kruskal();cout<<ans<<endl;sort(road.begin(),road.end(),cmp1);for(int i=0;i<road.size();i++){int type;if(road[i].type==1)type=1;else type=2;cout<<road[i].idx<<" "<<type<<endl;}return 0;
}
