[海军国际项目办公室]欢乐豆

2024-03-16 22:38

本文主要是介绍[海军国际项目办公室]欢乐豆,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

欢乐豆

题目概述

在这里插入图片描述
在这里插入图片描述

题解

首先可以发现一个性质,我们到任意一个未被更改所影响的节点上,不可能经过超过一条更改的边。
显然,如果我中途需要经过一条未被修改的边,那么我一定可以在从这个点的出发点直接走这条边到达这个点,如果到其它点再走,那么我所需要走的边权肯定会更大。
于是,到任意一个未被更改所影响的节点上,未被更改的节点直接走 a i a_{i} ai的边就行了。而一个被更改所影响了的节点,则需要可以沿着最短路走到某个节点,再从那个节点走 a i a_{i} ai的边。
剩下的更改过的节点走到更改过的节点的最短路,与我们上面的目的是相仿的,所以事实上我们真正的难点就是求这个最短路。

如果你直接用 F l o y e d Floyed Floyed找最短路的话,是 O ( m 3 ) O\left(m^3\right) O(m3)的,只有 36 p t s 36pts 36pts,最多再加上一个可以直接 d i j dij dij的特殊性质 B B B
但实际上我们可以用线段树来模拟 d i j dij dij
我们对于每个点出发都做一次 d i j dij dij,更新到每个节点的最短路是用该节点去更新未被更新的节点的最短路。
我们发现,从一个点出发,只有到与它之间连边是被更改过的情况边权是独特的,否则边权都是 a i a_{i} ai
所以我们可以对于这些独特的边单点修改,对于其它点区间修改。
还有跳出去到未被更改的点再跳回来的情况,这种情况可以全局修改。
即使其它点的区间不一定是连续的,但由于我们的独特点只有 O ( m ) O(m) O(m)个,所以我们区间修改的区间也是 O ( m ) O(m) O(m)级别的。
所以做一次 d i j dij dij实际上是 O ( m log ⁡ m ) O\left(m\log\,m\right) O(mlogm)的。啊啊啊!!!
直接对于每个点都做一次 d i j dij dij就行了。

时间复杂度 O ( n + m 2 log ⁡ m ) O\left(n+m^2\log\,m\right) O(n+m2logm)

源码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define MAXM 6005
#define lowbit(x) (x&-x)
#define reg register
#define pb push_back
#define mkpr make_pair
#define fir first
#define sec second
#define lson (rt<<1)
#define rson (rt<<1|1)
typedef long long LL;
typedef unsigned long long uLL;       
const int INF=0x3f3f3f3f;   
const int mo=5e5+9;
const int inv2=499122177;
const double jzm=0.997;
const int zero=15;
const int lim=2500000;
const int orG=3,invG=332748118;
const double Pi=acos(-1.0);
const double eps=1e-5;
typedef pair<int,int> pii;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){_T f=1;x=0;char s=getchar();while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}x*=f;
}
template<typename _T>
void print(_T x){if(x<0){x=(~x)+1;putchar('-');}if(x>9)print(x/10);putchar(x%10+'0');}
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
int add(int x,int y,int p){return x+y<p?x+y:x+y-p;}
void Add(int &x,int y,int p){x=add(x,y,p);}
int qkpow(int a,int s,int p){int t=1;while(s){if(s&1)t=1ll*a*t%p;a=1ll*a*a%p;s>>=1;}return t;}
int n,m,a[MAXN],id[MAXN],ord[MAXM],idx;
int mna,val[MAXM],dis[MAXN];
bool key[MAXN];LL ans;
vector<pii>G[MAXM];
struct ming{int u,v,w;}s[MAXM];
bool cmp(int x,int y){return val[x]<val[y];}
class SegmentTree{private:int minn[MAXM<<2],lzy[MAXM<<2],maxx[MAXM<<2];bool cov[MAXM<<2];void pushup(int rt){minn[rt]=INF;cov[rt]=cov[lson]&cov[rson];maxx[rt]=0;if(!cov[lson])minn[rt]=min(minn[lson],minn[rt]),maxx[rt]=max(maxx[lson],maxx[rt]);if(!cov[rson])minn[rt]=min(minn[rson],minn[rt]),maxx[rt]=max(maxx[rson],maxx[rt]);}void pushdown(int rt){if(lzy[rt]<INF-1){if(!cov[lson])maxx[lson]=lzy[rt],minn[lson]=min(lzy[rt],minn[lson]),lzy[lson]=min(lzy[lson],lzy[rt]);if(!cov[rson])maxx[rson]=lzy[rt],minn[rson]=min(lzy[rt],minn[rson]),lzy[rson]=min(lzy[rson],lzy[rt]);lzy[rt]=INF;}}public:void build(int rt,int l,int r){maxx[rt]=minn[rt]=lzy[rt]=INF;cov[rt]=0;if(l==r)return ;int mid=l+r>>1;build(lson,l,mid);build(rson,mid+1,r);}void modify(int rt,int l,int r,int al,int ar,int aw){if(l>r||l>ar||r<al||al>ar||cov[rt])return ;if(al<=l&&r<=ar){minn[rt]=min(aw,minn[rt]);maxx[rt]=aw;lzy[rt]=min(lzy[rt],aw);return ;}int mid=l+r>>1;pushdown(rt);if(al<=mid)modify(lson,l,mid,al,ar,aw);if(ar>mid)modify(rson,mid+1,r,al,ar,aw);pushup(rt);}pii query(int rt,int l,int r){if(l==r)return mkpr(minn[rt],l);int mid=l+r>>1;pushdown(rt);if(!cov[lson]&&minn[lson]<=minn[rson])return query(lson,l,mid);return query(rson,mid+1,r);}void update(int rt,int l,int r,int ai){if(l>r||l>ai||r<ai)return ;if(l==r){minn[rt]=maxx[rt]=INF;cov[rt]=1;return ;}int mid=l+r>>1;pushdown(rt);if(ai<=mid)update(lson,l,mid,ai);if(ai>mid)update(rson,mid+1,r,ai);pushup(rt); } int queryMax(){return maxx[1];}
}T;
signed main(){freopen("happybean.in","r",stdin);freopen("happybean.out","w",stdout); read(n);read(m);mna=INF;for(int i=1;i<=n;i++)read(a[i]);for(int i=1;i<=m;i++){read(s[i].u),read(s[i].v);read(s[i].w);key[s[i].u]=key[s[i].v]=1;}for(int i=1;i<=n;i++)if(key[i])ord[++idx]=i,id[i]=idx;for(int i=1;i<=m;i++)G[id[s[i].u]].pb(mkpr(id[s[i].v],s[i].w));for(int i=1;i<=idx;i++)sort(G[i].begin(),G[i].end());for(int i=1;i<=n;i++)if(!key[i])mna=min(mna,a[i]);for(int i=1;i<=n;i++){if(!key[i]){ans+=1ll*a[i]*(n-1);continue;}T.build(1,1,idx);T.modify(1,1,idx,id[i],id[i],0);int minn=INF;for(int j=1;j<=idx;j++){pii t=T.query(1,1,idx);int u=t.sec;int siz=G[u].size(),las=0;dis[u]=t.fir;if(dis[u]<T.queryMax()){for(int k=0;k<siz;k++){int v=G[u][k].fir,w=G[u][k].sec;T.modify(1,1,idx,las+1,v-1,dis[u]+a[ord[u]]);T.modify(1,1,idx,v,v,dis[u]+w);las=v;}T.modify(1,1,idx,las+1,idx,dis[u]+a[ord[u]]);T.modify(1,1,idx,1,idx,dis[u]+a[ord[u]]+mna);}T.update(1,1,idx,u);ans+=1ll*dis[u];minn=min(minn,dis[u]+a[ord[u]]);}ans+=1ll*minn*(n-idx);}printf("%lld\n",ans);return 0;
}

谢谢!!!

这篇关于[海军国际项目办公室]欢乐豆的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/816956

相关文章

一文教你如何将maven项目转成web项目

《一文教你如何将maven项目转成web项目》在软件开发过程中,有时我们需要将一个普通的Maven项目转换为Web项目,以便能够部署到Web容器中运行,本文将详细介绍如何通过简单的步骤完成这一转换过程... 目录准备工作步骤一:修改​​pom.XML​​1.1 添加​​packaging​​标签1.2 添加

tomcat多实例部署的项目实践

《tomcat多实例部署的项目实践》Tomcat多实例是指在一台设备上运行多个Tomcat服务,这些Tomcat相互独立,本文主要介绍了tomcat多实例部署的项目实践,具有一定的参考价值,感兴趣的可... 目录1.创建项目目录,测试文China编程件2js.创建实例的安装目录3.准备实例的配置文件4.编辑实例的

springboot集成Deepseek4j的项目实践

《springboot集成Deepseek4j的项目实践》本文主要介绍了springboot集成Deepseek4j的项目实践,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价... 目录Deepseek4j快速开始Maven 依js赖基础配置基础使用示例1. 流式返回示例2. 进阶

SpringBoot项目启动报错"找不到或无法加载主类"的解决方法

《SpringBoot项目启动报错找不到或无法加载主类的解决方法》在使用IntelliJIDEA开发基于SpringBoot框架的Java程序时,可能会出现找不到或无法加载主类com.example.... 目录一、问题描述二、排查过程三、解决方案一、问题描述在使用 IntelliJ IDEA 开发基于

SpringBoot项目使用MDC给日志增加唯一标识的实现步骤

《SpringBoot项目使用MDC给日志增加唯一标识的实现步骤》本文介绍了如何在SpringBoot项目中使用MDC(MappedDiagnosticContext)为日志增加唯一标识,以便于日... 目录【Java】SpringBoot项目使用MDC给日志增加唯一标识,方便日志追踪1.日志效果2.实现步

Ubuntu中Nginx虚拟主机设置的项目实践

《Ubuntu中Nginx虚拟主机设置的项目实践》通过配置虚拟主机,可以在同一台服务器上运行多个独立的网站,本文主要介绍了Ubuntu中Nginx虚拟主机设置的项目实践,具有一定的参考价值,感兴趣的可... 目录简介安装 Nginx创建虚拟主机1. 创建网站目录2. 创建默认索引文件3. 配置 Nginx4

SpringBoot项目启动错误:找不到或无法加载主类的几种解决方法

《SpringBoot项目启动错误:找不到或无法加载主类的几种解决方法》本文主要介绍了SpringBoot项目启动错误:找不到或无法加载主类的几种解决方法,具有一定的参考价值,感兴趣的可以了解一下... 目录方法1:更改IDE配置方法2:在Eclipse中清理项目方法3:使用Maven命令行在开发Sprin

Nginx实现高并发的项目实践

《Nginx实现高并发的项目实践》本文主要介绍了Nginx实现高并发的项目实践,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录使用最新稳定版本的Nginx合理配置工作进程(workers)配置工作进程连接数(worker_co

Vue项目的甘特图组件之dhtmlx-gantt使用教程和实现效果展示(推荐)

《Vue项目的甘特图组件之dhtmlx-gantt使用教程和实现效果展示(推荐)》文章介绍了如何使用dhtmlx-gantt组件来实现公司的甘特图需求,并提供了一个简单的Vue组件示例,文章还分享了一... 目录一、首先 npm 安装插件二、创建一个vue组件三、业务页面内 引用自定义组件:四、dhtmlx

SpringBoot项目注入 traceId 追踪整个请求的日志链路(过程详解)

《SpringBoot项目注入traceId追踪整个请求的日志链路(过程详解)》本文介绍了如何在单体SpringBoot项目中通过手动实现过滤器或拦截器来注入traceId,以追踪整个请求的日志链... SpringBoot项目注入 traceId 来追踪整个请求的日志链路,有了 traceId, 我们在排