bzoj2753: [SCOI2012]滑雪与时间胶囊

水深无声 2021-09-29 16:48 262阅读 0赞

这题真的很容易想到最小生成树。

而且题目有特别的性质，高处的连低处的是单向的，但是不会构环（老实讲一开始就是担心这个，但是现在发现好像没啥影响吧），所以其实先把能够访问的点dfs一次，排完序就直接搞好了。

#include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<cstdlib>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    typedef long long LL;
    
    LL h[1100000];
    
    struct node
    {
        int x,y,next;LL d;
    }a[2100000];int len,last[1100000];
    void ins(int x,int y,LL d)
    {
        len++;
        a[len].x=x;a[len].y=y;a[len].d=d;
        a[len].next=last[x];last[x]=len;
    }
    
    bool v[1100000];int cnt;
    void dfs(int x)
    {
        for(int k=last[x];k;k=a[k].next)
        {
            int y=a[k].y;
            if(v[y]==false)
            {
                v[y]=true;cnt++;
                dfs(y);
            }
        }
    }
    
    bool cmp(node n1,node n2)
    {
        return (h[n1.y]==h[n2.y])?(n1.d<n2.d):(h[n1.y]>h[n2.y]);
    }
    
    int fa[1100000];
    int findfa(int x)
    {
        if(fa[x]==x)return x;
        fa[x]=findfa(fa[x]);return fa[x];
    }
    int main()
    {
        int n,m,x,y;LL d;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            scanf("%lld",&h[i]), fa[i]=i;
        len=0;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%lld",&x,&y,&d);
            if(h[x]>=h[y])ins(x,y,d);
            if(h[y]>=h[x])ins(y,x,d);
        }
        memset(v,false,sizeof(v));
        v[1]=true;cnt=0;dfs(1);
        sort(a+1,a+len+1,cmp);
        
        LL sum=0;int edge=0;
        for(int k=1;k<=len;k++)
        {
            if(v[a[k].x]==true&&v[a[k].y]==true)
            {
                int fx=findfa(a[k].x),fy=findfa(a[k].y);
                if(fx!=fy)
                {
                    fa[fx]=fy;
                    sum+=a[k].d;
                    edge++;
                    if(edge==cnt)break;
                }
            }
        }
        printf("%d %lld\n",edge+1,sum);
        return 0;
    }

转载于:https://www.cnblogs.com/AKCqhzdy/p/8551491.html