[APIO2008]免费道路

并查集

题面

戳我

解析

先找出必须要的鹅卵石路。（可以通过先连上所有水泥路再看是否需要连鹅卵石路）
于是下一次，先连上必须要的鹅卵石路，再随便找水泥路连上。
因为每连一条路，都是把两个并查集连起来，没有优劣之分。
据说还要判图不联通的情况？？？

// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define inf 1000000009
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=5e5+100;
int n,m,k,u[N],v[N],c[N],num[2],u0[N],v0[N],c0[N],t,f[N];
bool vis[N];
il int gi()
{
  re int x=0,t=1;
  re char ch=getchar();
  while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
-----il int find(re int x){return f[x]==x?x:f[x]=find(f[x]);}-----
il void solve(re int ysn,re int mx)
{
  fp(i,1,m)
    if(c[i]==ysn&&num[ysn]<mx)
      {
        re int a=find(u[i]),b=find(v[i]);
    if(a^b)
      {
        f[a]=b;
        u0[++t]=u[i],v0[t]=v[i],c0[t]=c[i];
        vis[i]=1;num[ysn]++;
      }
      }
}
int main()
{
  n=gi();m=gi();k=gi();
  fp(i,1,m) u[i]=gi(),v[i]=gi(),c[i]=gi();
  scanf("%d%d%d",&n,&m,&k);
  fp(i,1,m) scanf("%d%d%d",&u[i],&v[i],&c[i]);
  fp(i,1,n) f[i]=i;
  num[0]=num[1]=0;
  solve(1,inf);solve(0,inf);
  if(num[1]+num[0]!=n-1||num[0]>k) {puts("no solution");return 0;}
  t=0;num[0]=num[1]=0;fp(i,1,n) f[i]=i;
  fp(i,1,m)
    if(!c[i]&&vis[i])
      {
        re int a=find(u[i]),b=find(v[i]);
    if(a^b)
      {
        f[a]=b;num[0]++;
        u0[++t]=u[i],v0[t]=v[i],c0[t]=c[i];
      }
      }
  solve(0,k);solve(1,inf);
  if(num[0]<k) {puts("no solution");return 0;}
  fp(i,1,t) printf("%d %d %d\n",u0[i],v0[i],c0[i]);
  return 0;
}