Description：

图中每条边边权为 $0$ 或 $1$ ，求图的一个 $0$ 边个数为 $k$ 的生成树。

$1\leqslant n\leqslant 20000,1\leqslant n\leqslant 1000000$

Solution：

先 $kruskal$ 一遍，尽量先选边权为 $1$ 的边，这样最后加入的边权为 $0$ 的边就是必须要加的边，把这些边在第二次 $kruskal$ 里把这些边先加进去，然后先尽量选边权为 $0$ 的边，知道加到了 $k$ 个，然后再加 $0$ 边，无解就是 $0$ 边不足 $k$ 个，尽量选 $0$ 边选不到 $k$ 个，和图不连通。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m,k;

#define MAXN 20010

#define MAXM 100010

struct edge

{

	int u,v,w;

}e[MAXM];

bool cmp_w(edge a,edge b){return a.w > b.w;}

bool cmp_r_w(edge a,edge b){return a.w < b.w;}

int f[MAXN];

int find(int x){return (x == f[x] ? x : f[x] = find(f[x]));}

edge s[MAXM];

int top = 0;

edge ans[MAXM];

int anstot = 0;

int main()

{

	scanf("%d%d%d",&n,&m,&k);

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);

	}

	sort(e + 1,e + 1 + m,cmp_w);

	for(int i = 1;i <= n;++i)f[i] = i;

	int tot = n;

	for(int i = 1;i <= m;++i)

	{

		int p = find(e[i].u),q = find(e[i].v);

		if(p == q)continue;

		f[p] = q;--tot;

		if(e[i].w == 0)

		{

			s[++top] = e[i];

		}

	}

	if(tot != 1 || top > k)

	{

		puts("no solution");

		return 0;

	}

	for(int i = 1;i <= n;++i)f[i] = i;

	for(int i = 1;i <= top;++i)

	{

		int p = find(s[i].u),q = find(s[i].v);

		f[p] = q;

		ans[++anstot] = s[i];

	}

	sort(e + 1,e + 1 + m,cmp_r_w);

	for(int i = 1;i <= m;++i)

	{

		int p = find(e[i].u),q = find(e[i].v);

		if(p == q)continue;

		if(e[i].w == 1)

		{

			f[p] = q;

			ans[++anstot] = e[i];

		}

		else

		{

			if(top < k)

			{

				f[p] = q;

				++top;

				ans[++anstot] = e[i]; 

			}

		}

	}

	if(top < k)

	{

		puts("no solution");

		return 0;

	}

	for(int i = 1;i <= anstot;++i)

	{

		printf("%d %d %d\n",ans[i].u,ans[i].v,ans[i].w);

	}

	return 0;

}