先计算至少需要多少鹅卵石路才能使得图连通，设为A，再计算总共有多少鹅卵石路，设为B。有解当且仅当A<=K<=B。
如果有解，先将必须的鹅卵石路加入，然后再加入一些鹅卵石路，使得一共加入了K条鹅卵石路。（注意，它们不能成环）。然后再加公路，同样不能成环。
然后，需要用到并查集。
CO
/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2010-4-21
DESCRIPTION:
$DESCRIPTION
*/
#include <stdio.h>
#include <string.h>
#define MAXN 20000
#define MAXM 100000
//begin set
int set[MAXN];
int get_set(int u)
{
if (set[u]) return set[u]=get_set(set[u]);
else return u;
}
int is_friend(int u,int v)
{
return get_set(u)==get_set(v);
}
void union_set(int u,int v)
{
//if (is_friend(u,v)) return;
set[get_set(u)]=get_set(v);
}
//end set
struct Edge{int u,v,c;};
int N,M,K;
Edge edge[MAXM];
bool must[MAXM];
int top;
Edge print[MAXN];
int main()
{
//freopen(“roads.in”,”r”,stdin);
//freopen(“roads.out”,”w”,stdout);
scanf(“%d %d %d\n”,&N,&M,&K);
for (int i=0;i<M;i++)
scanf(“%d %d %d\n”,&edge[i].u,&edge[i].v,&edge[i].c);
for (int i=0;i<M;i++)
if (edge[i].c)
if (!is_friend(edge[i].u,edge[i].v))
union_set(edge[i].u,edge[i].v);
for (int i=0;i<M;i++)
if (!edge[i].c)
if (!is_friend(edge[i].u,edge[i].v))
{
union_set(edge[i].u,edge[i].v);
must[i]=true;
print[top++]=edge[i];
}
if (top>=K) printf(“no solution\n”);
else
{
memset(set,0,sizeof(set));
for (int i=0;i<M;i++)
if (must[i])
if (!is_friend(edge[i].u,edge[i].v))
union_set(edge[i].u,edge[i].v);
for (int i=0;i<M;i++)
if (!must[i])
if (!is_friend(edge[i].u,edge[i].v))
{
union_set(edge[i].u,edge[i].v);
print[top++]=edge[i];
}
for (int i=0;i<top;i++)
printf(“%d %d %d\n”,print[i].u,print[i].v,print[i].c);
}
//fclose(stdin);
//fclose(stdout);
return 0;
}