首页 > 代码库 > BZOJ 2753 滑雪与时间胶囊(最短路-克鲁斯卡尔)
BZOJ 2753 滑雪与时间胶囊(最短路-克鲁斯卡尔)
题目链接: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());}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。