做会计需要了解的网站及软件,查pv uv的网站,做个网站要多少钱,沈阳企业网站制作哪家好题目描述 a180285非常喜欢滑雪。他来到一座雪山#xff0c;这里分布着M条供滑行的轨道和N个轨道之间的交点#xff08;同时也是景点#xff09;#xff0c;而且每个景点都有一编号i(1≤i≤N)和一高度Hi。a180285能从景点ii滑到景点j当且仅当存在一条i和j之间的边#xf…题目描述 a180285非常喜欢滑雪。他来到一座雪山这里分布着M条供滑行的轨道和N个轨道之间的交点同时也是景点而且每个景点都有一编号i(1≤i≤N)和一高度Hi。a180285能从景点ii滑到景点j当且仅当存在一条i和j之间的边且i的高度不小于j。 与其他滑雪爱好者不同a180285喜欢用最短的滑行路径去访问尽量多的景点。如果仅仅访问一条路径上的景点他会觉得数量太少。于是a180285拿出了他随身携带的时间胶囊。这是一种很神奇的药物吃下之后可以立即回到上个经过的景点不用移动也不被认为是a180285 滑行的距离。请注意这种神奇的药物是可以连续食用的即能够回到较长时间之前到过的景点比如上上个经过的景点和上上上个经过的景点。 现在a180285站在11号景点望着山下的目标心潮澎湃。他十分想知道在不考虑时间胶囊消耗的情况下以最短滑行距离滑到尽量多的景点的方案即满足经过景点数最大的前提下使得滑行总距离最小。你能帮他求出最短距离和景点数吗 输入格式 输入的第一行是两个整数N,M。 接下来1行有N个整数Hi分别表示每个景点的高度。 接下来M行表示各个景点之间轨道分布的情况。每行3个整数Ui,Vi,Ki。表示编号为Ui的景点和编号为Vi的景点之间有一条长度为Ki的轨道。 输出格式 输出一行表示a180285最多能到达多少个景点以及此时最短的滑行距离总和。 题解 对于高度不同的两点他们之间的边是有向的对于同于高度的点有边就可以互相到达我们只需要选取最短的一些边使他们仍联通即可。 若按照正常思路以边权排序直接跑Kruskal的话会发现可能出现有下面的点连接上面的点如他会直接选取两条边权为5的边 我们考虑如何消除高度的影响我们以终点高度为第一关键字边权为第二关键字排序那么就不可能出现上面的情况因为他会先选20的边。 相当于选点是逐层进行的上面的点一定会先被选取所以这个点选了之后不可能再连一条向上的边。 接着愉快地打出了代码。 #includebits/stdc.h
using namespace std;
#define ll long longconst int maxn1000005;
int n,m;
ll ans;
int fa[maxn],h[maxn];
struct edge{int x,y;ll k;
}a[maxn];templateclass Tinline void read(T x){x0;char chgetchar();while(!isdigit(ch)) chgetchar();while(isdigit(ch)) {x(x1)(x3)(ch^48);chgetchar();}
}void swap(ll x,ll y){ll tx;xy;yt;}bool cmp(edge a,edge b){if(h[a.y]h[b.y]) return a.kb.k;return h[a.y]h[b.y];
}int find(int x){if(fa[x]x) return x;return fa[x]find(fa[x]);
}void kruskal(){sort(a1,am1,cmp);int k0;for(int i1;im;i){int dxfind(a[i].x),dyfind(a[i].y);if(dx!dy){fa[dx]dy;ansa[i].k;k;}if(kn-1) break;;}printf(%d %lld,k1,ans);
}int main(){read(n);read(m);for(int i1;in;i) read(h[i]),fa[i]i;for(int i1;im;i){int x,y,z;read(x);read(y);read(z);if(h[x]h[y]) swap(x,y);a[i](edge){x,y,z};}kruskal();
} View Code 然后。。。。。 我们会发现是什么没考虑到呢接着便可以发现可能有出发点达不到的地方这些地方是没用的。 那么就可以考虑记录1可以利用的边用这些边跑Kruskal。在最初读入时对于高度不同的点建有向边 高度相同建双向边跑一边dfs要判断是否遍历过。 #includebits/stdc.h
using namespace std;
#define ll long longconst int maxn1000005;
int n,m,_n1,cnt;
ll ans;
int fa[maxn],h[maxn];
bool vis[maxn];
vectorpairint,ll e[maxn];
struct edge{int x,y;ll k;
}a[maxn];templateclass Tinline void read(T x){x0;char chgetchar();while(!isdigit(ch)) chgetchar();while(isdigit(ch)) {x(x1)(x3)(ch^48);chgetchar();}
}void swap(ll x,ll y){ll tx;xy;yt;}bool cmp(edge a,edge b){if(h[a.y]h[b.y]) return a.kb.k;return h[a.y]h[b.y];
}int find(int x){if(fa[x]x) return x;return fa[x]find(fa[x]);
}void kruskal(){sort(a1,acnt1,cmp);int k0;for(int i1;icnt;i){int dxfind(a[i].x),dyfind(a[i].y);if(dx!dy){fa[dx]dy;ansa[i].k;k;}if(k_n-1) break;}printf(%d %lld,_n,ans);
}void dfs(int u,int f){for(unsigned int i0;ie[u].size();i){int ve[u][i].first;if(vf) continue;a[cnt](edge){u,v,e[u][i].second};if(!vis[v]){vis[v]true;_n;dfs(v,u);}}
}int main(){read(n);read(m);for(int i1;in;i) read(h[i]),fa[i]i;for(int i1;im;i){int x,y,z;read(x);read(y);read(z);if(h[x]h[y]) swap(x,y);e[x].push_back(make_pair(y,z));if(h[x]h[y]) e[y].push_back(make_pair(x,z));}vis[1]true;dfs(1,0);kruskal();
} View Code 转载于:https://www.cnblogs.com/sto324/p/11172209.html
