最小生成树题一

时间:2021-08-19 21:35:54

生成树一

题目描述

给你云朵的个数NN,再给你MM个关系,表示哪些云朵可以连在一起。

现在小杉要把所有云朵连成KK个棉花糖,一个棉花糖最少要用掉一朵云,小杉想知道他怎么连,花费的代价最小。

链接

分析:

经过luogu题解的洗礼,使我懂得了....(病句,记下来,要考的 0.0)
仔细想想哭如斯卡尔的实现过程....
它一开始实际上就是把每个点看成独立的一棵树,其实每一步建边都保证了当前的所有生成树花费最小。重点: 每次合并都少1棵生成树
在此题中,就是n个云朵,划分成k个棉花糖,需连n-k条边。只需记录生成树的个数num,在合并时num--即可

#include<cstdio>
#include<algorithm>
using namespace std;

#define MAXN 1000+99
#define MAXM 10000+99

int n,m,k; 
int fa[MAXN];

struct edge{
    int x,y,val;
    bool operator < (const edge& xx) const {
        return val < xx.val ;
    }
}e[MAXM]; 

int find(int x) {
    return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);
}

int kruskal() {
    int num = n;
    int fax,fay,ans = 0; 
    for(int i = 1; i <= m; i++) {
        if(num <= k) break;//这里写的是<=,想想为啥 (提示;看看下面的判断 
        fax = find(e[i].x) ,fay = find(e[i].y) ;
        if(fax != fay) {
            fa[fax] = fay;
            ans += e[i].val ;
            num--;
        }
    }
    if(num == k) return ans;
    else return -1; 
}

int main() {
    scanf("%d%d%d",&n,&m,&k);
    for(int i = 1; i <= n; i++) fa[i] = i;
    for(int i = 1; i <= m; i++) scanf("%d%d%d",&e[i].x, &e[i].y, &e[i].val );
    sort(e+1, e+1+m);
    int ans = kruskal();
    printf("%d",ans);
}