锐客网

  1. 首页 > it技术 > >

NOIP2018|生成树 SCOI 2012 滑雪与时间胶囊

题意：一个图，每个点有一个高度 HiH i ，边有边权。从 11 号点开始，每次从 ii 走到 jj 当且仅当存在一条 ii 和 jj 之间的边，且 Hi>=HjH i >= H j 。当到达任意一个点时，可以 00 花费回到之前走到的任意一个点。要求满足经过点数最大的前提下使得经过的总距离最小，求最大点数和最短距离。
首先是建图：对于读入的每一条边，如果 Hi>=HjH i >= H j .，就连一条 i到ji 到 j 的有向边。如果 Hi<=HjH i <= H j ，就连一条 j到ij 到 i 的有向边。这样如果 Hi=HjH i = H j ， i,ji , j 之间就有一条双向边。
我们发现，回到之前走过的点，其实就是回溯的过程，所以我们从 11 号节点开始 dfsd f s ，对于搜到的点，我们将它加入到新图中，统计搜到的点的数量，就是最终要求的最大点数。
【NOIP2018|生成树 SCOI 2012 滑雪与时间胶囊】接下来我们在新图上跑 KruskalK r u s k a l 求最小生成树。对于排序部分，为保证有尽可能多的点在最小生成树里，我们按点的高度为第一关键字从大到小排序，边长为第二关键字从小到大排序，做最小生成树时累计边权求和即可。

#include using namespace std; struct node { int from,next,to; long long dis; }e[2001000]; struct tree { int x,y; long long c; }a[2001000]; int n,m,num,head[200100],cnt,sum=1; int f[201000],h[200100]; bool vis[1001000]; void add(int from,int to,long long dis) { e[++num].next=head[from]; e[num].from=from; e[num].to=to; e[num].dis=dis; head[from]=num; } void dfs(int x) { vis[x]=1; for(int i=head[x]; i; i=e[i].next) { int v=e[i].to; a[++cnt].x=x; a[cnt].y=v; a[cnt].c=e[i].dis; if(!vis[v]) { sum++; dfs(v); } }} int find(int x) { if(x==f[x]) return x; else { f[x]=find(f[x]); return f[x]; } } bool cmp(tree n1,tree n2) { if(h[n1.y]!=h[n2.y]) return h[n1.y]>h[n2.y]; else return n1.c>n>>m; for(int i=1; i<=n; ++i) scanf("%d",&h[i]); for(int i=1; i<=m; ++i) { int x,y; long long d; scanf("%d%d%lld",&x,&y,&d); if(h[x]>=h[y]) add(x,y,d); if(h[x]<=h[y]) add(y,x,d); } dfs(1); sort(a+1,a+cnt+1,cmp); for(int i=1; i<=n; ++i) f[i]=i; for(int i=1; i<=cnt; ++i) { int fx=find(a[i].x); int fy=find(a[i].y); if(fx!=fy) { f[fx]=fy; ans+=a[i].c; t++; if(t==sum-1) break; } } cout<" "

    推荐阅读


    上一篇：hdoj1244_Max Sum Plus Plus Plus（dp）

    下一篇：设计一个算法将两个字符串合并按字母排序