%%%\(\sf{ZYD\;\;TQL}\)
感觉这个题的题意有点难懂，简单概括一下就是：
有\(n\)个村庄，\(m\)条道路，道路分为水泥路和鹅卵石路，选择其中\(n-1\)条路使得所有村庄联通，并且选择的路中恰好有\(k\)条鹅卵石路。
我们可以先对所有的水泥路跑一遍\(Kruskal\)，把它们全加入生成树，然后再对鹅卵石路跑一遍，此时加进生成树里的鹅卵石路是必须要加的，因为没有它们，是无法让图联通的
之后我们将图复原，先将必须要加的鹅卵石路加进去，再添加鹅卵石路，直至总数达到\(k\)，最后再加水泥路。
无解的情况有：
- 找不到生成树
- 必须添加的鹅卵石路大于\(k\)
- 鹅卵石路的数量小于\(k\)
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int fa[20010];
struct zzz{
int f,t; bool fl;
}e1[100010],e2[100010],imp[20010],ans[20010];
int find(int x){
return fa[x]==x? x:fa[x]=find(fa[x]);
}
int cnt,tot1,tot2,tot3;
int read(){
int k=0; char c=getchar();
for(;c<'0'||c>'9';) c=getchar();
for(;c>='0'&&c<='9';c=getchar())
k=k*10+c-48;
return k;
}
int main(){
int n=read(),m=read(),k=read();
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++){
int x=read(),y=read();
if(read()) e2[++tot2].f=x,e2[tot2].t=y;
else e1[++tot1].f=x,e1[tot1].t=y;
}
if(tot1<k){
printf("no solution"); return 0;
}
for(int i=1;i<=tot2;i++){
int x=find(e2[i].f),y=find(e2[i].t);
if(fa[x]!=fa[y]) fa[x]=fa[y],cnt++;
}
for(int i=1;i<=tot1;i++){
int x=find(e1[i].f),y=find(e1[i].t);
if(x!=y){
fa[x]=fa[y],cnt++;
imp[++tot3]=e1[i];
}
}
if(cnt<n-1||tot3>k){
printf("no solution"); return 0;
}
cnt=0;
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=tot3;i++){
int x=find(imp[i].f),y=find(imp[i].t);
if(fa[x]!=fa[y]){
fa[x]=fa[y]; cnt++;
ans[cnt]=imp[i]; ans[cnt].fl=0;
}
}
for(int i=1;i<=tot1;i++){
int x=find(e1[i].f),y=find(e1[i].t);
if(fa[x]!=fa[y]){
fa[x]=fa[y]; cnt++;
ans[cnt]=e1[i]; ans[cnt].fl=0;
}
if(cnt==k) break;
}
if(cnt<k){
printf("no solution"); return 0;
}
for(int i=1;i<=tot2;i++){
int x=find(e2[i].f),y=find(e2[i].t);
if(fa[x]!=fa[y]){
fa[x]=fa[y]; cnt++;
ans[cnt]=e2[i]; ans[cnt].fl=1;
}
if(cnt==n-1) break;
}
for(int i=1;i<=n-1;i++)
printf("%d %d %d\n",ans[i].f,ans[i].t,ans[i].fl);
return 0;
}