首页 > 代码库 > BZOJ 2753 滑雪与时间胶囊（最短路-克鲁斯卡尔）

BZOJ 2753 滑雪与时间胶囊（最短路-克鲁斯卡尔）

2024-07-09 00:14:02   224人阅读

题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=2753

题意：一个n个点m条边的带权无向图，每个点有一个高度值h。某个从1号点开始遍历，每次走的边u到v，必须满足h[u]>=h[v]。已知从当前点回到曾经遍历过的任意一个点是不需要走路的。求最多可以遍历多少个点？遍历这些点走的最小路程是多少？

思路：只记录h[u]>=h[v]的 边，因为其他边是无用的，这样其实是个有向图。首先从1BFS一次可以得到多少个点可以到达。然后将边排序，对于边<u,v,w>按照 h[v]降序排序，然后h[v]相等的按照w升序。这样用克鲁斯卡尔并查集一下就行。

 

struct node{    int u,v,w,next;};node edges[N<<1];int head[N],e;void Add(int u,int v,int w){    edges[e].u=u;    edges[e].v=v;    edges[e].w=w;    edges[e].next=head[u];    head[u]=e++;}int a[N];i64 dis[N];int n,m,visit[N];int cmp(node p,node q){    return a[p.v]>a[q.v]||a[p.v]==a[q.v]&&p.w<q.w;}int f[N];int get(int x){    if(f[x]!=x) f[x]=get(f[x]);    return f[x];}i64 cal(){    sort(edges,edges+e,cmp);    int i;    FOR1(i,n) f[i]=i;    int x,y,u,v;    i64 ans=0;    FOR0(i,e)    {        u=edges[i].u;        v=edges[i].v;        if(!visit[u]||!visit[v]) continue;        x=get(u);        y=get(v);        if(x!=y) f[x]=y,ans+=edges[i].w;    }    return ans;}int main(){    RD(n,m);    int i;    FOR1(i,n) RD(a[i]);    int x,y,w;    clr(head,-1);    FOR1(i,m)    {        RD(x,y,w);        if(a[x]>=a[y]) Add(x,y,w);        if(a[y]>=a[x]) Add(y,x,w);    }    queue<int> Q;    int cnt=0;    Q.push(1);    visit[1]=1;    while(!Q.empty())    {        x=Q.front();        Q.pop();        cnt++;        for(i=head[x];i!=-1;i=edges[i].next)        {            y=edges[i].v;            if(!visit[y]) visit[y]=1,Q.push(y);        }    }    printf("%d %lld\n",cnt,cal());}

 

 

 


联系
我们