【[APIO2008]免费道路】

\(kruskal\)好题

\(0\)边的数量在某些情况下是可以无限制的调控的，前提是所有必须存在的边都在生成树里了

所以应该分别求出有哪些边是必须在生成树里的，我们可以先从大到小排序，求出有哪些\(0\)边必须在生成树里，之后再从小到大排序，求出那些\(1\)边必须在生成树里

之后剩下的边就可以随便放了，调控\(0\)边的个数恰好为\(k\)即可

代码

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cstdio>

#define LL long long

#define re register

#define maxn 20005

struct E

{

	int u,v,w;

}e[100005],Ans[100005];

inline int read()

{

	char c=getchar();

	int x=0;

	while(c<'0'||c>'9') c=getchar();

	while(c>='0'&&c<='9')

		x=(x<<3)+(x<<1)+c-48,c=getchar();

	return x;

}

int fa[maxn],sz[maxn];

int n,m,tot,k,num;

inline void Rebuild() { for(re int i=1;i<=n;i++) fa[i]=i,sz[i]=1; }

int find(int x)

{

	if(x==fa[x]) return x;

	return fa[x]=find(fa[x]);

}

inline int merge(int x,int y)

{

	int xx=find(x),yy=find(y);

	if(xx==yy) return 0;

	if(sz[xx]>sz[yy]) fa[yy]=xx,sz[xx]+=sz[yy];

		else fa[xx]=yy,sz[yy]+=sz[xx];

	return 1;

}

inline int cmp1(E A,E B)

{

	return A.w<B.w;

}

inline int cmp2(E A,E B)

{

	return A.w>B.w;

}

int main()

{

	n=read(),m=read(),k=read();

	for(re int i=1;i<=m;i++) e[i].u=read(),e[i].v=read(),e[i].w=read();

	Rebuild();

	std::sort(e+1,e+m+1,cmp2);

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

		if(merge(e[i].u,e[i].v)&&!e[i].w)

			Ans[++tot].u=e[i].u,Ans[tot].v=e[i].v,Ans[tot].w=0,num++;

	if(tot>k)

	{

		puts("no solution");

		return 0;

	}

	std::sort(e+1,e+m+1,cmp1);

	Rebuild();

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

		if(merge(e[i].u,e[i].v)&&e[i].w)

			Ans[++tot].u=e[i].u,Ans[tot].v=e[i].v,Ans[tot].w=1;

	Rebuild();

	for(re int i=1;i<=tot;i++)

		merge(Ans[i].u,Ans[i].v);

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

	{

		if(!e[i].w&&num>=k) continue;

		if(merge(e[i].u,e[i].v))

		{

			if(!e[i].w&&num<k) num++;

			Ans[++tot].u=e[i].u,Ans[tot].v=e[i].v,Ans[tot].w=e[i].w;

		}

	}

	if(tot!=n-1||num<k) puts("no solution");

	else for(re int i=1;i<=tot;i++) printf("%d %d %d\n",Ans[i].u,Ans[i].v,Ans[i].w);

	return 0;

}