新亚（New Asia）王国有 N 个村庄，由 M 条道路连接。其中一些道路是鹅卵石路，而其它道路是水泥路。保持道路免费运行需要一大笔费用，并且看上去 王国不可能保持所有道路免费。为此亟待制定一个新的道路维护计划。
国王已决定保持尽可能少的道路免费，但是两个不同的村庄之间都应该一条且仅由一条 且仅由一条免费道路的路径连接。同时，虽然水泥路更适合现代交通的需 要，但国王也认为走在鹅卵石路上是一件有趣的事情。所以，国王决定保持刚好 K 条鹅卵石路免费。
举例来说，假定新亚王国的村庄和道路如图 3(a)所示。如果国王希望保持两 条鹅卵石路免费，那么可以如图 3(b)中那样保持道路(1, 2)、(2, 3)、(3, 4)和(3, 5) 免费。该方案满足了国王的要求，因为：(1)两个村庄之间都有一条由免费道 路组成的路径；(2)免费的道路已尽可能少；(3)方案中刚好有两条鹅卵石道路 (2, 3)和(3, 4)
Solution
题意:有黑白两种边，求一科最小生成树使他恰好有k条百边
直接先选k条白边再加黑边是错的，因为加完之后图可能不连通，所以我们先要弄清楚哪些白边是必须加的。
我们先对所有黑边做生成树，在对白色边跑一遍，这样我们就求出了哪些白边是必须要加的。
然后我们再跑一遍生成树，先把必须加的加上，再把K条白边补齐，最后再跑黑边。
接下来就是恶心的判不合法环节，
如果图不连通，GG。
如果必须加的边大与k，GG。
如果加的边到不了k，GG。
Code
#include<iostream> #include<cstdio> #define N 20002 #define M 100002 using namespace std; int f[N],n,m,num,k,kk,tot,tot1,kkk; bool t[M]; struct node{ int u,v; }e[M],g[M]; int find(int x){return f[x]=f[x]==x?x:find(f[x]);} int main(){ scanf("%d%d%d",&n,&m,&k);kkk=kk=k;int u,v,tag; for(int i=1;i<=m;++i){ scanf("%d%d%d",&u,&v,&tag); if(tag)e[++tot].u=u,e[tot].v=v; else g[++tot1].u=u,g[tot1].v=v; } for(int i=1;i<=n;++i)f[i]=i; for(int i=1;i<=tot;++i){ u=find(e[i].u),v=find(e[i].v); if(u!=v){ f[u]=v; num++; } } for(int i=1;i<=tot1;++i){ u=find(g[i].u);v=find(g[i].v); if(u!=v){ f[u]=v; t[i]=1; num++;k--; } } if(num!=n-1||k<0){ printf("no solution "); return 0; } num=0; for(int i=1;i<=n;++i)f[i]=i; for(int i=1;i<=tot1;++i)if(t[i]){ u=find(g[i].u);v=find(g[i].v); f[u]=v;kk--;num++; } for(int i=1;i<=tot1;++i)if(!t[i]){ if(!kk)break; u=find(g[i].u);v=find(g[i].v); if(u!=v){f[u]=v;kk--;num++;} } for(int i=1;i<=tot;++i){ u=find(e[i].u),v=find(e[i].v); if(u!=v){f[u]=v;num++;} } if(num!=n-1||kk){ printf("no solution "); return 0; } for(int i=1;i<=n;++i)f[i]=i; for(int i=1;i<=tot1;++i)if(t[i]){ u=find(g[i].u);v=find(g[i].v); f[u]=v;kkk--;printf("%d %d 0 ",g[i].u,g[i].v); } for(int i=1;i<=tot1;++i)if(!t[i]){ if(!kkk)break; u=find(g[i].u);v=find(g[i].v); if(u!=v){ f[u]=v; kkk--;printf("%d %d 0 ",g[i].u,g[i].v); } } for(int i=1;i<=tot;++i){ u=find(e[i].u),v=find(e[i].v); if(u!=v){ f[u]=v; printf("%d %d 1 ",e[i].u,e[i].v); } } return 0; }