每日一题（牛客） — 2020 - 05 -01

最小生成树的题目，其实发现自己对一些算法的时间复杂度的计算不怎么好，还是要练一下，不过这题挺不错，是最小生成树的加强版

题目链接

自己的想法

• 这题自己看大体知道是最小生成树，也知道是找与1相连的图，但是不太会整
• 一部分是忘记最小生成树他的排序（知道是从小到大，但是那是裸最小生成树），然后就是不太会处理他的集合
• 看大佬的思路和代码后才能白了

解题思路：

• 首先我们存储的时候要注意他是个有向图，从高到低才能走过
• 然后是找出他们的集合，然后存储起来，这里我们要记录他的个数，因为要输出他最多到达的地方
• 然后我们就进入kruskal， 这里的排序我们按照y的排即可，因为x --> y 肯定是从高到低，因此我们按照y的高度排，那么肯定都是到低的，如果高度相同，那么我们就按照路程的长短排序，小的排在前面（这里需要思考理解一下）
• 然后套板子即可。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;

const int N = 1000010, M = 2000010;

int h[N], ne[M], e[M], ww[M], p[N], a[N]， cnt, idx;

bool st[N];

void add(int x, int y, int z){
    e[idx] = y, ne[idx] = h[x], ww[idx] = z, h[x] = idx++;
}

struct Edge{
    int x, y, w;
}edges[M];

bool cmp(Edge xx, Edge yy){
    if (a[xx.y] == a[yy.y]){
        return xx.w < yy.w;
    }
    return a[xx.y] > a[yy.y];
}

void add1(int x, int y, int z){
    edges[cnt].x = x, edges[cnt].y = y,edges[cnt++].w = z;
}

int Find(int x ){
    if (p[x] != x) p[x] = Find(p[x]);
    return p[x];
}

void bfs(){
    queue<int> q;
    q.push(1);
    int res1 = 1;
    st[1] = true;
    while(!q.empty()){
        int t = q.front();
        q.pop();
        for (int i = h[t];i != -1; i = ne[i]){
            int j = e[i];
            add1(t,j,ww[i]); 
            if (!st[j]){
                q.push(j);
                res1++;
                st[j] = true;
            }
        }
    } 
    printf("%d ",res1);
}

void kruskal(){
    sort(edges,edges + cnt,cmp);
    long long res = 0;
    int num = 0;

    for (int i = 0; i < cnt; i++){
        int x = edges[i].x, y = edges[i].y, w = edges[i].w;
        if (Find(x) != Find(y)){
            p[Find(x)] = Find(y);
            num ++;
            res += w;
        }
    }

    printf("%lld\n",res);
}

int main(){

    memset(h,-1,sizeof h);

    int n, m;
    scanf("%d%d",&n,&m);
    for (int i = 1; i <= n; i++){
        scanf("%d",&a[i]);
    }

    for (int i = 1; i <= n ;i ++){
        p[i] = i;
    }

    for (int i = 0; i < m; i++){
        int x, y, z;
        scanf("%d%d%d",&x,&y,&z);
        if (a[x] > a[y]) add(x,y,z);
        else if (a[x] == a[y]){
            add(x,y,z);
            add(y,x,z);
        }
        else add(y,x,z);
    }
    bfs();
    kruskal();
    return 0;
}