Cptraser/ 十月 28, 2018/ 2018.10/ 0 comments

[SCOI2012]滑雪与时间胶囊

题面传送门

第一问很好做,BFS就好了,DFS会爆栈,顺便处理能用的边。
以所到点的高度为第一关键字,边权为第二关键字排序,做Kruskal
这样做可以满足达到所有可到点的同时边权和最小。

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

char tc(){static char tr[10000],*A=tr,*B=tr;return A==B&&(B=(A=tr)+fread(tr,1,10000,stdin),A==B)?EOF:*A++;}
void read(int &x){char c;for(;!isdigit(c=tc()););for(x=c-48;isdigit(c=tc());x=(x<<1)+(x<<3)+c-48);}

long long Ans=0;
int N,M,x,y,v,H[100005],_Ans,vis[100005],Lik,Fa[100005];
int head[100005],nxt[2000005],to[2000005],w[2000005],Cnt;
#define Add(x,y,c) (nxt[++Cnt]=head[x],to[Cnt]=y,w[Cnt]=c,head[x]=Cnt)
struct Node{
    int x,y,c;
    bool operator<(const Node&P)const{
        return H[y]>H[P.y] || H[y]==H[P.y]&&c<P.c;
    }
}E[4000005];


int q[100005];
void bfs(){
    int l=0,r=1;
    q[1]=1;vis[1]=1;_Ans=1;
    while (l<r){
        int x=q[++l];
        for(int p=head[x];p;p=nxt[p])if(!vis[to[p]])
            q[++r]=to[p],vis[to[p]]=1,_Ans++;
    }
}
int G(int x){return x==Fa[x]?x:Fa[x]=G(Fa[x]);}
int main()
{
    read(N),read(M);
    for(int i=1;i<=N;i++)read(H[i]),Fa[i]=i;
    for(int i=1;i<=M;i++){
        read(x),read(y),read(v);
        if(H[x]>=H[y])Add(x,y,v);
        if(H[y]>=H[x])Add(y,x,v);
    }
    bfs();printf("%d ",_Ans);
    for(int i=1;i<=N;i++)if(vis[i])
        for(int j=head[i];j;j=nxt[j])if(vis[to[j]]){
            if(H[i]>=H[to[j]])E[++Lik]=(Node){i,to[j],w[j]};
            if(H[i]<=H[to[j]])E[++Lik]=(Node){to[j],i,w[j]};
        }
    sort(E+1,E+Lik+1);
    for(int i=1;i<=Lik;i++){
        int x=G(E[i].x),y=G(E[i].y);
        if(x^y)Ans+=E[i].c,Fa[x]=y;
    }
    printf("%lld",Ans);
}
Share this Post

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*