Description
solution
正解：贪心+kruskal
分析发现，有一些石路是必须走的，我们首先找出所有这样的石路，方法是把所有的水泥路加进去，然后再加入石路，可以得出至少需要的石路的数量，我们判断这个数量有没有超过K，然后我们再判断是否可以刚好达到K，以上就是无解的情况，我们再加入几条必须的石路后再任意加入到K条，剩下再加入水泥路得出方案.
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define RG register
#define il inline
#define iter iterator
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int N=100005;
int n,m,K;
struct node{
int x,y,z;
}e[N];
struct Ans{
int x,y,z;
Ans(){}
Ans(int _x,int _y,int _z){x=_x;y=_y;z=_z;}
void pri(){printf("%d %d %d
",x,y,z);}
}a[N];
int fa[N],sum[N],tot=0;bool d[N];
il int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void solve(bool t,int lim){
RG int x,y,z;
for(int i=1;i<=m;i++){
x=e[i].x;y=e[i].y;z=e[i].z;
if(z==t && sum[z]<lim){
if(find(x)==find(y))continue;
fa[find(y)]=find(x);sum[t]++;
a[++tot]=Ans(x,y,z);
if(t==0)d[i]=true;
}
}
}
void work()
{
RG int i;
scanf("%d%d%d",&n,&m,&K);
for(i=1;i<=n;i++)fa[i]=i;
for(i=1;i<=m;i++)
scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z);
solve(1,N);solve(0,N);
if(sum[0]+sum[1]<n-1 || sum[0]>K){puts("no solution");return ;}
sum[0]=sum[1]=tot=0;
for(i=1;i<=n;i++)fa[i]=i;
for(i=1;i<=m;i++){
if(!d[i])continue;
fa[find(e[i].y)]=find(e[i].x);sum[0]++;
a[++tot]=Ans(e[i].x,e[i].y,e[i].z);
}
solve(0,K);
if(sum[0]!=K){puts("no solution");return ;}
solve(1,N);
for(i=1;i<=tot;i++)a[i].pri();
}
int main()
{
work();
return 0;
}