Kruskal+Greedy

这个题目还是一个比较有意思的题目啦。
我们想解决这个问题还是需要一点前置知识的。
首先我们来讲一下最小生成树的一些概念。已经有所了解的小伙伴可以直接跳到分割线后

最小生成树

首先我通俗讲一讲现在比较主流的一些最小生成树的做法。
①prim算法。这个是一个基于加入点的做法了，并且写起来的的话和求最短路算法的dijkstra的代码看起来挺像的。什么意思呢？就是我们要迭代n次，并且是妥妥的n-1次，因为每一次是要把不在当前集合的点里面挑一个距离最小的点来加入进来，所以一共有n个点的话，就一定是迭代n次（这里默认我第一个点已经没有加进来，这个地方和dijkstra不一样），这个做法的话时间复杂度其实是O(N^2),对于这个题目其实不好（这里小小的吐槽一下题目里好像没有给我们n,m数据范围），我查了一下大概是n<=100000的，那么这样的话n^2的时间复杂度达到了1e10,妥妥的会超时，不可取，PASS。看下一个算法吧。
②第二个算法就是Kruskal算法，这个算法和prim不一样在于，他不是每一次找一个点，而是找一条边，首先要去给你的所有边排个序，时间复杂度是O(mlogm)，就是很普通的排序的时间复杂度了，然后，在遍历一遍你的所有边，时间复杂度是O(m)，说明kruskal是O（mlogm+m）的，题目数据范围大概是m<=1000000，算了一下mlogm大概是2*10^7这样的话还是能接受的，我们果断选Kruskal.

具体做法

补了一点最小生成树的知识之后，言归正传，我们这个题目，我们有两问，一个是问你从1出发的最大连通块的的数量是多大？
这个还是比较简单，我们bfs搜索一遍就好了（温馨提示：要记录是否访问过这个点）。
第二问是要求最小生成树
这里先发表一点我的看法，对于做图论题，其实难点不在于前置知识和代码手法，其实这个都可以背个板子就行，难在你要首先发现一个正确的做法，比如在这个题目，舍去prim使用Kruskal，然后你还要理解每一个基础算法的原理是什么，不能随便乱套板子。这个题目就很明显是反映了理解的作用。
首先要注意到一点：

这句话的意思是，我们首先保证点的数量最大，然后在这个基础上去寻找一个最小生成树。
具体做法是：我们首先通过bfs求出来从一出发的可以到达的点的数量。然后记录在这个最小生成树的所有点。在写Kruskal的时候，我们只要对于那些边的端点都在最小生成树的边加以处理就可以了。这道题目的关键就是对边拍一个序了，我们首先看高度，如果你能到达一个点的高度大于你能到达一个点的另一个高度，由于贪心的思想你肯定会选择更高的，这样对于后面选点有帮助，然后高度一样的话，我们对权值从小到大排个序，这个很显然，最小生成树肯定要最小的嘛。然后还有很多的小细节，我就放在代码里面注释了~~
还有要注意的是最小生成树有可能爆int 所以最好long long
详情见代码

code

#include<bits/stdc++.h>
using namespace std;
int h[100010],cnt,n,m;//点的高度
vector<int> e[100010];//存所有的邻接点
int f[100010]; //是并查集，存父亲节点
int ecnt;//用来记录有多少条边，不是每一条边都要加进来，具体可以看下面main函数的加边的操作
long long ans=0;//存你的最小生成树的答案
bool vis[100010];//记录你的那些在最小生成树的点
struct node{
    int height,a,b,w;//存这个边的到达的点的高度，出点，入点和权值
}edge[2000010];
void bfs()//bfs求从1 出发的可到达的点
{
    cnt=0;
    queue<int> q;
    q.push(1);
    vis[1]=true;
    cnt++;
    while(q.size())
    {
        int t=q.front();
        q.pop();

        for(auto x:e[t])if(!vis[x]) q.push(x),vis[x]=true,++cnt;//能到达的就vis记录下来
    }
}
int find(int x) {return f[x]==x?x:f[x]=find(f[x]);}//并查集的基本操作，寻找祖先
void kruskal()
{
    ans=0;
    int now=0;
    for(int i=1;i<=n;i++) f[i]=i;
    sort(edge,edge+ecnt,[](node a,node b){if(a.height==b.height )return a.w<b.w;else return a.height>b.height;});//这个是c++11的lambda表达式操作，不熟悉的小伙伴可以自行百度了解一下，对所有的边排序

    for(int i=0;i<ecnt;i++)
    {
        int a=edge[i].a,b=edge[i].b,w=edge[i].w;
    //    cout<<"bian<"<<a<<' '<<b<<endl;
        if(!(vis[a]&&vis[b])) continue;//必须要两个点都在最小生成树的集合里面
        if(find(a)!=find(b)) {
            ans+=w;
            ++now;
            f[find(b)]=find(a);//合并
        }
        //if(now==cnt-1) break;
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",h+i);//输入高度
    int now=0;
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if(h[a]>=h[b]) edge[ecnt++]={h[b],a,b,c},e[a].push_back(b);//如果a高度大于等于b说明可以到达
        if(h[b]>=h[a]) edge[ecnt++]={h[a],b,a,c},e[b].push_back(a);//原理同上
    }
    bfs();
    cout<<cnt<<' ';

    kruskal();
    cout<<ans;
    return 0;

}