首先让我们来介绍Krukal算法，他是一种用来求解最小生成树问题的算法，首先把边按边权排序，然后贪心得从最小开始往大里取，只要那个边的两端点暂时还没有在一个联通块里，我们就把他相连，只要这个图里存在最小生成树我们就一定可以找到他。（证明：首先如果我们没有选最小的边，那么他一定可以踢掉其他的边来使生成树更小，于是最小一定取，那么接下来能取的边同理，以此类推我们证毕。）
这个算法其实不要紧，但是他这种利用边的置换的思想，与得到最小生成树的定性，才是我们真正的收获。
【BZOJ 3654】tree
这道题在思路上还是很清晰的，他保证存在了，那么我们就是找最小的就可以。那么我们先把边排序，跑Kruskal，然后通过二分给白边加权，然后再求最小生成树，慢慢使我们的白边树逼近需要就是了，因为他说一定存在，所以你二分到小一点就多，大一点就少的情况就可以看你取边顺序直接取一个值就好了。
#include <cstdio>
#include <algorithm>
inline void read(int &sum){
register char ch=getchar();
for(sum=;ch<''||ch>'';ch=getchar());
for(;ch>=''&&ch<='';sum=(sum<<)+(sum<<)+ch-'',ch=getchar());
}
const int N=;
const int M=;
struct E{
int a,b,w,c;
}e[M];
int f[N],h[];
inline int find(int x){
return f[x]==x?x:(f[x]=find(f[x]));
}
int n,m,need;
inline bool comp(E a,E b){
return a.w+h[a.c]<b.w+h[b.c]||(a.w+h[a.c]==b.w+h[b.c]&&a.c<b.c);
}
inline int get_ans(int &get){
for(int i=;i<=n;i++)f[i]=i;
std::sort(e+,e+m+,comp);
register int x,y,w,c,hav=,ret=,whi=;
for(int i=;i<=m;i++){
x=e[i].a+,y=e[i].b+,w=e[i].w,c=e[i].c;
if(find(x)==find(y))continue;
f[find(x)]=find(y);
ret+=w+h[c],whi+=c,hav++;
if(hav==n-)break;
}
get=hav-whi;
return ret;
}
int main(){
read(n),read(m),read(need);
for(int i=;i<=m;i++)
read(e[i].a),e[i].a++,read(e[i].b),e[i].b++,read(e[i].w),read(e[i].c);
int mid,l=-,r=,ans,get;
while(l<=r){
mid=(l+r)>>,h[]=mid;
int ret=get_ans(get);
if(get>=need)
ans=ret-need*h[],l=mid+;
else r=mid-;
}
printf("%d",ans);
return ;
}
【BZOJ 3654】tree
【BZOJ 3624】[Apio2008]免费道路
这道题的思维就要比上道题，大得多。首先鹅卵石边数不够 PASS！！！，然后不联通 PASS！！！。现在我们就可以用一种特殊的方法来试图找到我们想要的边数，我们发现如果我们把水泥路分成两半，一半放在鹅卵石前（鹅卵石连续），另一半放在鹅卵石后，然后跑类Krusal（其实一样只是不是求最小），那么随着前一半长度减小，鹅卵石边数单调不减，且最小变化幅度小于等于1，所以如果存在我们一定可以找到那种方案（为什么呢，如果我们把水泥路鹅卵石路分别都视为一类，不管具体是什么，那么显然成立，那么如果我们关注他们具体是谁就要考虑到他们顺序问题，然而实际上并没有关系），如果不存在直接 PASS ！！！
然而如果我们知道这个的话，就会发现，其实我们只要判断一下题目中的k在不在先鹅卵石再水泥和先水泥再鹅卵石围成的区间里就好了。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ft first
#define sd second
#define abs(a) ((a)<0?-(a):(a))
#define mmp(a,b) std::make_pair((a),(b))
typedef std::pair<int,int> pii;
const int N=;
const int M=;
int f[N],n,m,m0,m1,k;
pii use[M],ger[M],cct[M];
int in[M];
inline int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
inline void Unit(int x,int y){f[find(x)]=find(y);}
inline bool judge(){
if(k>m0)return true;int ret=;
for(int i=;i<=n;++i)
if(find(i)==i)++ret;
return ret>;
}
inline int check(int pos){
for(int i=;i<=n;++i)f[i]=i;
for(int i=;i<=pos;++i)use[i]=cct[i];
for(int i=;i<=m0;++i)use[i+pos]=ger[i];
for(int i=pos+;i<=m1;++i)use[m0+i]=cct[i];
memset(in,-,sizeof(in));int ret=,have=;
for(int i=;i<=m&&have<n;++i){
if(find(abs(use[i].ft))==find(use[i].sd))continue;
if(use[i].ft>)in[i]=,++ret;
else in[i]=;
Unit(abs(use[i].ft),use[i].sd),++have;
}//printf("<%d %d>\n",pos,ret);
return ret;
}
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=;i<=n;++i)f[i]=i;
for(int i=,x,y,z;i<=m;++i){
scanf("%d%d%d",&x,&y,&z);
if(z)cct[++m1]=mmp(-x,y);
else ger[++m0]=mmp(x,y);
Unit(x,y);
}if(judge()){puts("no solution");return ;}
int l=,r=m1,mid;
bool ans=false;
while(l<=r){
mid=(l+r)>>;
int ret=check(mid);
if(ret==k){ans=true;break;}
if(ret>k)l=mid+;
else r=mid-;
}if(!ans){puts("no solution");return ;}
for(int i=;i<=m;++i)
if(in[i]!=-)
printf("%d %d %d\n",abs(use[i].ft),use[i].sd,in[i]);
return ;
}