[vijos1234]口袋的天空<最小生成树>

题目链接：https://vijos.org/p/1234

白天刚刚写完prim的算法，晚上就心血来潮的打了一道最小生成树的题

虽然有题解说可以用prim做，但是这道题明显是加最小的边，感觉kruskal方便多了

但是愉快的是我竟然不是一次过，最后发现是题意理解问题，我之前读了很多遍题，还是以为n朵云不用用完，但其实是n朵云要用完并成为k个棉花糖

首先可以知道的是，k个棉花糖中有k-1个是单个的云，因为单个的云就是不要花费的，所以生成树就是在剩下的n-k+1朵云中产生，然后这n-k+1朵云最多用n-k+1-1条边连接是最优的，所以其实就是kruskal选出n-k+1-1条边的最小价值

然后就是一个裸的kruskal了，然后由于很久没打kruskal了，我竟然自作聪明的加了vis数组，然后光荣爆零，最后删去vis，只用并查集判断就瞬间a了

果然是我太弱了吗

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 #include<cstdlib>

 #define maxn 10005

 using namespace std;

 struct edge{

     int  u,v,w;

 }e[*maxn];

 int n,m,k,pos,tot,ans;

 int head[maxn],fa[maxn];

 int read(){

     int xx=,ff=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')ff=-;ch=getchar();}

     while(ch>=''&&ch<=''){xx=xx*+ch-'';ch=getchar();}

     return xx*ff;

 }

 void adde(int u,int v,int w){

     e[++pos].u=u;

     e[pos].v=v;e[pos].w=w;

 }

 int comp(const void*a,const void*b){

     return (*(struct edge*)a).w>(*(struct edge*)b).w?:-;

 }

 int find_(int x){

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

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

 } 

 int main(){

     scanf("%d",&n);m=read();k=read();

     for(int i=;i<=m;i++){

         int u,v,w;

         u=read();v=read();w=read();

         adde(u,v,w);

     }

     if(k>n){

         printf("No Answer");return ;

     }

     for(int o=;o<=n;o++)

         fa[o]=o;

     qsort(e,m+,sizeof(e[]),comp);

     for(int i=;i<=m;i++){

         int u=e[i].u,v=e[i].v;

         int fu=find_(u);int fv=find_(v);

         if(fu!=fv){

             fa[fu]=fv;

             tot++;vis[fv]=;ans+=e[i].w;

         }

         if(tot>=n-k+-){

             printf("%d",ans);return ;

         }

     }

     printf("No Answer");

 }

kruskal

【总结】

头可断，血可流，代码错不得

注意判断选入边的条件，理解并查集的运用，不能死记硬背

巴特西

[vijos1234]口袋的天空<最小生成树>

最新文章

热门文章