2016/06/25
诸老师讲的图论，听了这道题很想写一下，但是看来要留到期末考后了。
07/01
有的标记是说生成树，有的是并查集。。。然而我只是觉得这棵奇怪的生成树蛮精妙的。。。
题目比较难过的只是K的限制，要读清楚题意，像我一开始就没有注意第一要求是“免费道路尽量少”。。。
至于这个K，可大可小。。最好的做法便是先将所有的水泥路连上，找到“必须需要的鹅卵石路”。。。
然后按照K的限制一条条地加。。。代码写的有些臭长。。。因为一个月没写代码了。。。又把==写成了=
判断no solution的时候忘记压缩路径了。。。又要debug。。。。。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 200000
using namespace std;
int bian[N],f[N],uu[N],vv[N],need[N];
int n,m,k,all,al;
int find(int x)
{
if(f[x]!=x)f[x]=find(f[x]);return(f[x]);
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
;i<=n;i++)f[i]=i;int u,v,w;
memset(need,,sizeof(need));
;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);bian[i]=w;uu[i]=u;vv[i]=v;
){
int x=find(u),y=find(v);
if(x!=y)f[x]=y;
}else all++;
}
;i<=m;i++)
)
{
int x=find(uu[i]),y=find(vv[i]);
,f[x]=y,al++;
}
if(al>k||all<k){
printf(;
}
;i<=n;i++)f[i]=i;
;i<=m;i++)
{
)
{
int x=find(uu[i]),y=find(vv[i]);if(x!=y)f[x]=y;
}
}
;i<=m;i++)
&&bian[i]==)
{
,al++;
}
if(al<k){
printf(;
}
;i<=m;i++)
)
{
;
}
);
;i<=n;i++)if(x!=find(i)){
printf(;}
;i<=m;i++)
)printf("%d %d %d\n",uu[i],vv[i],bian[i]);
}