\(\\\)
一个\(N\)个点\(M\)条边的图，每条边可以选择\(w_i,p_i\)两个边权之一，现求一个生成树上的最大边权最小值，要求这棵生成树上至少有\(K\)条边选择的是\(w_i\)权值。\(Luogu\)上还要以"选了哪些编号的边，每条边选择的是哪种权值"的形式求输出方案。
- \(N\in [1,10^4]\)，\(M\in [0,2\times 10^4]\)，\(K\in [0,N-1]\)，\(w_i,p_i\in [1,3\times 10^4]\)
\(\\\)
\(Solution\)
- 最小生成树变形。先将边按照\(w_i\)排序，按照\(kruskal\)的方式连上\(K\)条边，再按照\(min(w_i,p_i)\)排序，连完剩下的所有边，注意第一遍连上的边要打上标记，避免使用了两次。答案即为所有连过的边中边权最大值，还要注意处理\(K=0\)和\(K=N-1\)的两种情况。
- 关于输出方案，每次记录一下就好，注意第二遍扫描的时候也可能取第一类权值。
\(\\\)
\(Code\)
#include#include #include #include #include #include #include #define N 10010#define M 20010#define R register#define gc getcharusing namespace std;inline int rd(){ int x=0; bool f=0; char c=gc(); while(!isdigit(c)){if(c=='-')f=1;c=gc();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();} return f?-x:x;}int n,m,k,cnt,res,tot;struct edge{int x,y,w1,w2,num;}e[M];struct result{int p,x;}ans[N];inline bool cmp1(edge x,edge y){return x.w1