P2916 [USACO08NOV]Cheering up the Cow G 题解
2022/4/6 23:23:18
本文主要是介绍P2916 [USACO08NOV]Cheering up the Cow G 题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
前置知识:最小生成树算法(Kruskal/Prim)
例题
算法分析:
这一道题中给出一个无向图,求从任意一点开始经过每一点的最短路径。
既然要经过每一个点,还要求最短路径,算法就是最小生成树了。
我用的是 Kruskal 算法。
有一点需要注意:每条路的长度需要如何计算?
约翰需要经过每一条道路两次,并且每走一次,就需要安慰这条路后的奶牛,所以路径长度=道路长度*2+安慰两头奶牛时间
代码如下:(因为几乎是 Kruskal 模板,所以没有注释)
#include<bits/stdc++.h> using namespace std; typedef long long LL; struct node { LL x,y,dis; }a[100000+10]; LL n,p,c[10000+10],fa[10000+10],t,ans; bool cmp(node fir,node sec) { return fir.dis<sec.dis; } LL gf(LL x) { if(fa[x]==x) return x; return fa[x]=gf(fa[x]); } int main() { scanf("%lld%lld",&n,&p); for(int i=1;i<=n;i++) scanf("%lld",&c[i]); for(int i=1;i<=p;i++) { scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].dis); a[i].dis=a[i].dis*2+c[a[i].x]+c[a[i].y]; } for(int i=1;i<=n;i++) fa[i]=i; sort(a+1,a+p+1,cmp); for(int i=1;t<n-1;i++) { int fx=gf(a[i].x); int fy=gf(a[i].y); if(fx!=fy) { fa[fx]=fy; ans+=a[i].dis; t++; } } sort(c+1,c+n+1); printf("%lld\n",ans+c[1]); return 0; }
这篇关于P2916 [USACO08NOV]Cheering up the Cow G 题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升